[BOJ 24649 // C++] Letters Q and F

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 24649번 문제인 Letters Q and F이다.
문제는 아래 링크를 확인하자.

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

 

주어진 Q와 F의 모양은 두 번째 열의 첫째 행부터 셋째 행까지를 중점적으로 볼 때 항상 검은칸-흰칸-검은칸 구조를 가지고 있어야 함을 관찰하자.

 

위 관찰을 이용하면, 오른쪽부터 색칠된 칸들을 살펴볼 때 검은칸-흰칸-검은칸 구조가 나올 때마다 이 구조가 Q에 포함되는 구조일 수 있는지 먼저 판단하고, 그 다음으로 이 구조가 F에 포함될 수 있는 구조인지 판단하는 것을 반복해나가는 것으로 문제를 해결할 수 있음을 유추할 수 있다. Q에 포함될 수 있는 구조인데 지나치면 Q에 포함되는 마지막 열 검은 칸이 이후에 어떤 문자에도 포함될 수가 없어짐을 확인하자. 이와 유사하게 F의 경우도 정당성을 보일 수 있다.

 

아래는 제출한 소스코드이다.

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

int R, C;
string board[300];
int Q, F;

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

	cin >> R >> C;
	for (int r = 0; r < R; r++) cin >> board[r];

	for (int c = C - 2; c > 0; c--) {
		for (int r = 1; r + 3 < R; r++) {
			if (board[r - 1][c] == '#' && board[r][c] == '.' && board[r + 1][c] == '#') {
				if (board[r][c + 1] == '#') {
					if (board[r - 1][c - 1] == '#' && board[r - 1][c] == '#' && board[r - 1][c + 1] == '#' && board[r][c - 1] == '#' && board[r][c + 1] == '#' && board[r + 1][c - 1] == '#' && board[r + 1][c] == '#' && board[r + 1][c + 1] == '#' && board[r + 2][c + 1] == '#' && board[r + 3][c + 1] == '#') {
						Q++;
						board[r - 1][c - 1] = board[r - 1][c] = board[r - 1][c + 1] = board[r][c - 1] = board[r][c + 1] = board[r + 1][c - 1] = board[r + 1][c] = board[r + 1][c + 1] = board[r + 2][c + 1] = board[r + 3][c + 1] = '.';
					}
				}
				else {
					if (board[r - 1][c - 1] == '#' && board[r - 1][c] == '#' && board[r - 1][c + 1] == '#' && board[r][c - 1] == '#' && board[r + 1][c - 1] == '#' && board[r + 1][c] == '#' && board[r + 2][c - 1] == '#' && board[r + 3][c - 1] == '#') {
						F++;
						board[r - 1][c - 1] = board[r - 1][c] = board[r - 1][c + 1] = board[r][c - 1] = board[r + 1][c - 1] = board[r + 1][c] = board[r + 2][c - 1] = board[r + 3][c - 1] = '.';
					}
				}
			}
		}
	}

	cout << Q << ' ' << F;
}