*[백준][1343] 폴리오미노

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

1343번: 폴리오미노

문제

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

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

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

입력

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

출력

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

 

해결 방법

1. 연속 된 X의 갯수를 체크하여 .이 나올 경우 또는 문자열의 끝인 경우에 바꿔치기를 시전하였다. 

2. 연속된 X의 갯수가 홀수이면 보드판을 AAAA, BB로 덮을 수 없게 된다.

3. 가능 한 경우 AAAA에 우선순위를 높여 보드판을 덮도록 하였다. 

 

소스코드

#include <stdio.h>
#include <string>
#include <iostream>
using namespace std;
bool solution(string &answer, int &count) 
{
	while (count) {
		if (count - 4 >= 0) {
			answer += "AAAA";
			count -= 4;
		}
		else if (count - 2 >= 0) {
			answer += "BB";
			count -= 2;
		}
		else {
			return false;
		}
	}
	return true;
}

int main()
{
	string str;
	string answer = "";
	cin >> str;
	int count = 0;
	for (int i = 0; i < str.length(); i++) {
		if (str[i] == 'X') {
			count++;
		}
		else if (str[i] == '.') {
			if (!solution(answer ,count)) {
				printf("-1\n");
				return 0;
			}
			answer += ".";
		}
	}
	if (!solution(answer, count)) {
		printf("-1\n");
		return 0;
	}
	printf("%s\n", answer.c_str());
	return 0;
}

 

결과