[BaekJoon]1343번: 폴리오미노

그리디 알고리즘

문제

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

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

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

입력

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

출력

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

예제 입력 1 
XXXXXX

예제 출력 1 
AAAABB

💻코드

/*
	 [백준 1343] 폴리오미노
	  23-07-06 / c++

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

	  < 알고리즘 >
		그리디
		
		X의 개수를 세면서 될 수 있는 경우의 수(1,2,3,4)로 나누어 결과값을 만든다
		A가 B보다 우선되어야 하므로, X가 4인 경우를 먼저 따져준다.
		X가 1 또는 3이고, 그 다음 문자가 X가 아니면 -1을 출력한다.
 */

#include<iostream>
#include<string>

using namespace std;

#define	POLYOMINO_1 "AAAA"
#define	POLYOMINO_2 "BB"

int main(void) {
	int cntX = 0;		// X 개수
	string res = "";	// result

	// 입력 ex) "XXXX.XX..XXXX" --> 결과 "AAAA.BB..AAAA"
	string str;
	cin >> str;

	for (int i = 0; i < str.length(); i++) {
		if (str[i] == 'X') {
			cntX++;
			if (cntX == 4) {
				res += POLYOMINO_1;
				cntX = 0;
			}
			else if (cntX == 2 && str[i + 1] != 'X') {
				res += POLYOMINO_2;
				cntX = 0;
			}
			else if ((cntX == 3 || cntX == 1) && str[i + 1] != 'X') {
				break;
			}
		}
		else {
			res += '.';
		}
	}

	// X 개수가 홀수개면 다 덮을 수 없으므로 -1
	if (cntX % 2 != 0) res = "-1";

	cout << res;
	return 0;
}