[BOJ] 폴리오미노 1343번 C++

 

 

문제

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

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

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

입력

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

출력

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

 

접근 방식

 

입력받은 문자열을 돌면서 X라면 카운트값을 증가해주고 . 라면 분기처리를 해준다

만약 카운트값이 0이상이고 짝수면 반복문을 돌면서 AAAA 혹은 BB를 정답 문자열에 더해준다

만약 0이상인데 홀수면 AAAA, BB로 폴리오미노를 덮을 수 없으므로 -1을 출력하고 리턴해준다

그리고 마지막으로 . 을 정답문자열에 더해준다

 

그리고 문자열을 다 돌고도 카운트값이 0이상이면 마지막 문자열이 X로 끝났다는 의미이므로

위의 분기처리를 똑같이 반복해준다!

 

 

코드

 

#include<bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    string str; cin>>str;
    string ans = "";
    int cnt = 0 ;

    for(auto c : str) {
        if(c == 'X') {
            cnt++;
        }
        else {
            if(cnt > 0) {
                if(cnt % 2 == 1) {
                    cout<<-1;
                    return 0;

                }
                while(cnt > 0) {
                    if(cnt - 4 < 0) {
                        ans += "BB";
                        cnt -= 2;
                    }
                    else {
                        ans += "AAAA";
                        cnt -= 4;
                    }
                }
            }
            ans += '.';   
        }
    }
    if(cnt > 0) {
        if(cnt % 2 == 1) {
            cout<<-1;
            return 0;

        }
        while(cnt > 0) {
            if(cnt - 4 < 0) {
                ans += "BB";
                cnt -= 2;
            }
            else {
                ans += "AAAA";
                cnt -= 4;
                }
        }
    }

    if(ans.size() == 0) cout<<-1;
    else cout<<ans;
}