백준 23085 - 판치기(C++)

문제 링크입니다. https://www.acmicpc.net/problem/23085

23085번: 판치기

BFS를 통해 풀 수 있는 문제입니다.

문자열 X가 있다고 했을 때, 뒤집을 경우를 생각해보겠습니다.

예를 들어 X가 HHHHH라고 하겠습니다. 여기서 3번을 뒤집을 수 있다고 했을 때 나올 수 있는 경우는

HHKKK, HKKKH, KKKHH .... 등 있습니다. 그렇다면 이때 나오는 문자열들을 같은 것으로 생각해 보겠습니다.

 

위의 문자열들에서 H를 2개, K를 1개 뒤집는다고 한다면 H가 1개, K가 4개가 됩니다. 어떤 문자열이든 H와 K의 문자 갯수가 같습니다. 

이로서 알 수 있는 것은  H와 K를 통해 만들어진 문자열일뿐, K개의 원하는 것을 뒤집을 수 있기에 어떤 구성을 하든 이루어진 문자 갯수가 같다면 같은 문자열로 볼 수 있다는 것을 알 수 있습니다.

 

따라서 뒤집어진 코인의 갯수를 통해서 탐색을 하면 된다는 결론을 얻을 수 있습니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>

using namespace std;

int N, K;
string start;
int check[3001];

int bfs(int back, int cnt) {
	queue<pair<int, int>> q;
	check[back] = 1;
	q.push({ back, 0 });
	while (!q.empty()) {
		int back_coin = q.front().first;
		int front_coin = N - back_coin;
		int x = q.front().second;
		if (back_coin == N) return x;
		q.pop();
		for (int i = 0; i <= K; i++) {
			int reverse_back = i;
			int reverse_front = K - i;
			if (reverse_back > back_coin || reverse_front > front_coin) continue;
			if (check[back_coin - reverse_back + reverse_front] == 0) {
				check[back_coin - reverse_back + reverse_front] = 1;
				q.push({ back_coin - reverse_back + reverse_front , x + 1 });
			}
		}
	}
	return -1;
}

void solve() {
	int back = 0;
	for (int i = 0; i < start.size(); i++) {
		if (start[i] == 'T') back++;
	}
	int ans = bfs(back, 0);
	cout << ans;
}

int main() {
	cin.tie();
	cout.tie();
	cin >> N >> K;
	cin >> start;
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요