[Baekjoon/C++] 1343번 - 폴리오미노

[백준] Baekjoon Online Judge

문제로 이동

 

문제

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

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

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

 

입력

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

 

출력

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

 

---

풀이

#include <iostream>
using namespace std;

string cover(int cnt);

// 폴리오미노로 문자 덮기
string cover(int cnt) {
    string s = "";

    while (cnt >= 4) {
        s += "AAAA";
        cnt -= 4;
    }

    while (cnt > 0) {
        s += "BB";
        cnt -= 2;
    }

    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    string s;
    cin >> s;

    int cnt = 0;
    string result;

    for (int i = 0; i < s.length(); i++) {
        if (s[i] == 'X') cnt++;
        else {
            if (cnt % 2 == 1) break;

            result += cover(cnt);
            result += ".";

            cnt = 0;
        }
    }

    // 출력
    if (cnt % 2 == 1) cout << "-1\n";
    else {
        result += cover(cnt);

        cout << result << '\n';
    }

    return 0;
}

 

    int cnt = 0;
    string result;

    for (int i = 0; i < s.length(); i++) {
        if (s[i] == 'X') cnt++;
        else {
            if (cnt % 2 == 1) break;

            result += cover(cnt);
            result += ".";

            cnt = 0;
        }
    }

 X가 연속으로 몇 번 입력되었는지 계산한다. 그러다 '.'을 만나면 cnt가 홀수인지 확인하고 홀수라면 반복을 끝낸다. 민식이가 가지고 있는 폴리오미노는 "AAAA", "BB"로 둘다 짝수이기에 cnt가 홀수인 경우 보드판의 'X'를 모두 폴리오미노로 덮지 못하게 되기 때문이다.

 cnt가 짝수라면 cover함수를 호출하여 result에 폴리오미노로 덮은 문자열과 '.'을 더하고, cnt를 0으로 초기화한다.

 

// 폴리오미노로 문자 덮기
string cover(int cnt) {
    string s = "";

    while (cnt >= 4) {
        s += "AAAA";
        cnt -= 4;
    }

    while (cnt > 0) {
        s += "BB";
        cnt -= 2;
    }

    return s;
}

 사전순으로 가장 앞서는 답을 출력하기 위해서는 "AAAA"를 우선적으로 사용해야 한다. 그러므로 위의 함수에서도 최대한 "AAAA" 를 사용하고, 남는 칸에 "BB"를 사용하도록 했다.

 

    // 출력
    if (cnt % 2 == 1) cout << "-1\n";
    else {
        result += cover(cnt);

        cout << result << '\n';
    }

 답을 출력하는 부분의 코드이다. 입력 받은 문자열 s의 끝이 '.'이 아니라면 덮지 못한 보드칸이 존재하므로 cover()을 한 번 더 호출해야 한다.