취미로 코딩하기

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

이번에 볼 문제는 백준 11334번 문제인 Coin Turning Game이다.
문제는 아래 링크를 확인하자.

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

주어진 동전배치에서 어떤 한 구간을 뒤집어 나오는 동전배치도 그 배치로 시작해 이길 수 있는 경우가 존재한다면 현재의 동전배치는 이길 수 없는 동전배치이고, 그렇지 않다면 이길 수 있는 동전배치이다.

위와 같은 개념을 구간dp를 이용해 코드로 작성하고 문제를 해결하자.

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

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

string S; int slen;
map<string, bool> mp;
int ansL, ansR;

bool func(string& s) {
	if (mp.count(s)) return mp[s];

	for (int r = 0; r < slen; r++) {
		if (s[r] == 'H') {
			for (int l = r; l > -1; l--) {
				string ss = s;
				for (int i = l; i <= r; i++) {
					if (ss[i] == 'H') ss[i] = 'T';
					else ss[i] = 'H';
				}
				if (!func(ss)) {
					mp.insert(make_pair(s, 1));
					ansL = l, ansR = r;
					return 1;
				}
			}
		}
	}

	mp.insert(make_pair(s, 0));
	return 0;
}

void solve() {
	cin >> S; slen = S.length();
	if (mp.count(S)) mp.erase(S);
	if (func(S)) cout << "YES" << ' ' << ansR + 1 << ' ' << ansR - ansL + 1 << '\n';
	else cout << "NO\n";
}

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

	int T; cin >> T;
	while (T--) solve();
}