[백준] 23085번: 판치기

📌 문제

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

📌 설명

처음에 BFS인지 감도 안 잡히는 문제였다. BFS로 풀어야 한다는 것을 알아도 코드를 작성하기 힘들었다. 인터넷의 도움을 통해 어느 동전이 H고 T인지가 중요한 것이 아니라 H 또는 T 상태인 동전의 수가 중요하다는 것을 알았다. 초기 H의 상태와 뒤집은 횟수인 cnt을 큐에 넣고 BFS를 수행하여 H의 수가 동전의 수인 n과 같아지는 지점까지 수행하였다. 이때의 cnt값은 모든 동전을 뒷면으로 만드는 데 필요한 최소 횟수임이 자명하다. BFS 내부의 코드에서 for문을 수행하며 k개의 동전 중 몇 개의 H 상태 동전을 뒤집을지를 결정하였다.

📌 코드

#include <iostream>
#include <queue>
#include <string>

using namespace std;

int visited[3001];
int n, m;
string s;

int main() {
	cin >> n >> m >> s;

	int head = 0;
	for (int i = 0;i < n;i++) {
		if (s[i] == 'H')
			head++;
	}

	queue<pair<int, int>> q;
	q.push({ head, 0 });
	visited[head] = 1;
	while (!q.empty()) {
		int h = q.front().first;
		int t = n - h;
		int cnt = q.front().second;
		q.pop();

		if (t == n) {
			cout << cnt;
			return 0;
		}

		// 'H'인 동전을 뒤집을 개수
		for (int i = 1;i <= m;i++) {
			if (i <= h && m - i <= t) {
				if (!visited[h - 2 * i + m]) {
					visited[h - 2 * i + m] = 1;
					q.push({ h - 2 * i + m ,cnt + 1 });
				}
			}
		}
	}

	cout << -1;
}