[BOJ][C++] 백준 1343번: 폴리오미노 (Silver V)

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

 

문제

민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB
이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.
폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.

입력

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

출력

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

 

풀이

// 풀이 : https://whkakrkr.tistory.com

#include <bits/stdc++.h>

using namespace std;

string solution(string&board) {
    string ans = "";
    
    // 문자열을 숫자 벡터로
    vector<int>v;
    int cnt = board[0]=='X' ? 1 : 0;
    for(int i=1; i<board.size(); i++) {
        char c = board[i];
        if(c == 'X') {
            if(cnt == 0) {
                v.push_back(0);
            }
            cnt++;
        } else if(c == '.') {
            v.push_back(cnt);
            cnt = 0;
        }
    }
    v.push_back(cnt);
    
    // 벡터를 폴리오미노로 변환
    for(int i : v) {
        if(i==0) {
            ans += '.';
            continue;
        }
        
        if(i%2 == 1) {
            return "-1";
        }
        
        for(int j=0; j<i/4; j++) {
            ans += "AAAA";
        }
        if(i%4 == 2) {
            ans += "BB";
        }
    }

    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	
	string board;
	cin >> board;
	
	cout << solution(board);
	
    return 0;
}