[c++][그리디] 백준 1343번: 폴리오미노

 

 

 

 

 

 

 

 

문제 풀이

1. 문자열을 하나하나 살피며 X일 경우 count 증가, 아니면 개수를 세지 않는다.

2. ' . '을 만났을 경우

    2 - 1. ' . '을 만나면  폴리오미노로 덮을 수 없기 때문에 count를 0으로 변경한다. 이때 ' . '을 만나기 전에 폴리오미노로 덮을 수 있는 경우가 있을 수 있어 확인해준다. 만약 X의 개수가 2개이면 BB로 덮어준다.

3. X를 만났을 경우

    3 - 1. X의 개수가 4개가 되면 AAAA로 덮어주고 count를 0으로 변경한다.

    3 - 2. X의 개수가 4개가 되지도 ' . '을 만나지도 않고 문자열이 끝날 경우 

          3 - 2 - 1. X의 개수가 2개이면 BB로 덮어준다.

4. 위의 과정을 거친 후 문자열에 X가 남아 있으면 -1을 출력하고, 아니면 바꾼 결과를 출력한다.

 

 

 

코드

#include <iostream>

using namespace std;

int main() {
	string board;

	cin >> board;

	int count = 0;
	for (int i = 0; i < board.length(); i++) {
		count++; // 문자의 개수를 센다.

		if (board[i] == '.') {
			count--; // .이 나오면 개수를 세지 않는다
			if (count == 2) { // X의 개수가 2개일 때 .이 나왔을 경우
				board[i - 1] = 'B';
				board[i - 2] = 'B';
			}
			count = 0;
		}
		else {
			if (count == 4) { // X의 개수가 4개일 때
				board[i] = 'A';
				board[i - 1] = 'A';
				board[i - 2] = 'A';
				board[i - 3] = 'A';
				count = 0; // 폴리오미노로 덮었으므로 count는 0
			}
			if (i == board.length() - 1) { //.을 만나지도 x의 개수가 4개를 채우지도 못했을 경우
				if (count == 2) {
					board[i] = 'B';
					board[i - 1] = 'B';
				}
				count = 0;
			}
		}
	}

	if (board.find('X') != std::string::npos) // 문자열에 X가 하나라도 있으면 -1출력
		cout << "-1\n";
	else
		cout << board << "\n";

	return 0;
}