[C++백준 1343번:폴리오미노]

문제링크

https://www.acmicpc.net/problem/1343

1343번: 폴리오미노

문제

민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB

이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.

폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 500이다.

출력

첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.

 

해석

X의 개수가 2의 배수가 아니라면 가지고 있는 폴리오미노로 덮을 수 없다.

X의 개수가 2의 배수 일 때 개수가 4보다 크다면 AAAA로 덮어나가고 4보다 작아지면 BB로 덮어주면 된다. (이 때 남은 개수가 3이나 1이 될 수 없다. 앞에서 이미 2의 배수인지 체크했기 때문에)

코드

#include <iostream>
#include <string>
using namespace std;
 
int main() {
    string n;
    string output = "";
    cin >> n;
 
    int count = 0;
    for (int i = 0; i < n.size(); i++) {
        if (n[i] == 'X') {
            count++;
        }
        else {
            if (count % 2 != 0) {
                cout << -1;
                return 0;
            }
 
            while (count >= 4) {
                output = output + "AAAA";
                count = count - 4;
            }
 
            while (count > 0) {
                output = output + "BB";
                count = count - 2;
            }
 
            output = output + ".";
        }
    }
 
    if (count % 2 != 0) {
        cout << -1;
        return 0;
    }
 
    while (count >= 4) {
        output = output + "AAAA";
        count = count - 4;
    }
 
    while (count > 0) {
        output = output + "BB";
        count = count - 2;
    }
 
    cout << output;
}

 

Memo

좀 더 간결하게 작성할 수 있을 것 같다. 시간나면 코드를 다져보는 시간을 갖는것도 좋을 것 같다.