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

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

1343번: 폴리오미노

풀이 :

- X와 .로 이루어진 문자열이 주어지고, X는 A나 B로 덮어서 새로운 문자열을 만든 뒤 출력한다

- A와 B의 갯수가 4와 2로 짝수로만 주어지기 때문에 X의 갯수가 홀수라면 덮을 수 없고 -1일 출력한다

- .를 만나기 전까지 X의 갯수를 세어주고, .를 만나면 세어준 갯수에 따라 덮거나 반복문을 종료해준다.

 

코드 :

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main(){
    cin.tie(NULL);
    ios::sync_with_stdio(false);

	int cnt = 0; //X의 갯수를 세어줄 변수 선언
	string s, ans; //입력받을 문자열과 복사해준 문자열 선언
	bool res = true; //덮을 수 있는 문자열인지 아닌지 판별할 bool 변수 선언

	cin >> s;
	s += '.'; //마지막에 .이 와야 따로 검사하지 않게 됨
	for(int i=0; i<s.size(); i++){
		if(s[i] == 'X'){ //X가 나올 때는 카운트만 해준다
			cnt++;
		}else{ //.을 기준으로 cnt를 고려
			if(cnt > 0){ //cnt가 0보다 크다는건 직전 값이 X였다는 것
				if(cnt % 2 != 0){ //A와 B는 짝수라서 홀수일 경우 덮을 수 없다
					res = false; //따라서 res에 false 값 넣어주고 break한다
					break;
				}
				while(cnt){ //짝수일 경우 break되지 않아, cnt의 값이 0이 될 때가지 while문이 돈다.
					if(cnt/4 > 0){ //사전순으로 출력하라고 했기 때문에 4보다 크면 A부터 넣어줘야 한다
						ans += "AAAA";
						cnt -= 4;
					}else{ //4보다 작으면 B를 넣어준다
						ans += "BB";
						cnt -= 2;
					}
				}
			}
			ans += '.'; //.는 덮을 수 없기 때문에 .를 그대로 복사해준다
			cnt = 0;
		}
	}
	ans[ans.size()-1] = '\n'; //아까 검사를 위해 넣어준 .도 복사했기 때문에 개행문자로 바꿔준다
	(res ? cout << ans : cout << -1 << '\n'); //res의 값이 true일 경우 덮어씌어준 답을 출력하고, false라면 -1이 출력된다
}