(C++) - 백준(BOJ) 1343번 : 폴리오미노

www.acmicpc.net/problem/1343

1343번: 폴리오미노

greedy 문제였습니다.

 

풀이방법

 1. '.'이 있는 좌표, 끝에 도당했다면 끝의 좌표 + 1을 queue에 저장합니다.

 

 2. queue가 빌 때까지 다음을 수행합니다.

   2-1. piv를 4개씩 보고 옮겨주면서 queue front()까지 "AAAA"를 정답 변수 ans에 붙입니다.

   2-2. piv를 2개씩 보고 옮겨주면서 queue front()까지 "BB"를 정답 변수 ans에 붙입니다.

   2-3. '.'을 ans에 붙입니다.

   2-4. piv를 queue의 front() + 1로 갱신해줍니다.

   2-5. pop()해줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
string board;
string ans;
queue <int> dots;
int piv;
int main(){
    cin >> board;
    for(int i = 0; i < board.size(); i++){
        if(board[i] == '.') dots.push(i);
        if(i == board.size() - 1) dots.push(i + 1);
    }
    while(!dots.empty()){
        int cnt = 0;
        for(int i = piv; i < dots.front(); i++){
            cnt++;
            if(cnt == 4){
                ans += "AAAA";
                cnt = 0;
                piv = i + 1;
            }
           
        }
        
        cnt = 0;
        for(int i = piv; i < dots.front(); i++){
            cnt++;
            if(cnt == 2){
                ans += "BB";
                cnt = 0;
                piv = i + 1;
            }
        }
        if(cnt) { cout << -1; return 0;}
        if(dots.front() < board.size() && board[dots.front()] == '.') ans += '.';
        piv = dots.front() + 1;
        dots.pop();
    }
   
    cout << ans << '\n';
}