[백준/BOJ] 백준 2600번 : 구슬게임

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

2600번: 구슬게임

 

cache[k1에 남아있는 구슬의 수][k2에 남아있는 구슬의 수][현재 플레이어가 누구인지] = 승리하면 1, 패배하면 -1을 저장하여 다이나믹 프로그래밍과 게임 이론을 통해 문제를 해결했다.

 

코드

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

vector<int> b;
int k1, k2;
int cache[505][505][2];
vector<char> result;

void Pre() {
	for (int i = 0; i < 505; i++) {
		for (int j = 0; j < 505; j++) {
			for (int k = 0; k < 2; k++) {
				cache[i][j][k] = -2;
			}
		}
	}
}

//here_order가 0이면 A, 1이면 B
//현재 상황에서 here_order가 승리하면 1, 패배하면 -1 반환
int Solve(int remain_k1, int remain_k2, int here_order) {

	int& ret = cache[remain_k1][remain_k2][here_order];

	if (ret != -2) {
		return ret;
	}

	int check = 987654321;
	for (int i = 0; i < 3; i++) {
		int this_b = b[i];

		//남은 k1에서 this_b만큼 꺼낼 수 있을때
		if (remain_k1 >= this_b) {

			//상대가 지는 경우를 찾아야 한다

			if (here_order == 0) {
				check = min(check, Solve(remain_k1 - this_b, remain_k2, 1));
			}

			else {
				check = min(check, Solve(remain_k1 - this_b, remain_k2, 0));
			}
		}

		//남은 k2에서 this_b만큼 꺼낼 수 있을때
		if (remain_k2 >= this_b) {

			//상대가 지는 경우를 찾아야 한다

			if (here_order == 0) {
				check = min(check, Solve(remain_k1, remain_k2 - this_b, 1));
			}

			else {
				check = min(check, Solve(remain_k1, remain_k2 - this_b, 0));
			}
		}
	}

	if (check == -1) { //상대가 지는 경우가 있을때
		ret = 1; //자신은 이길 수 있다
	}

	else { //상대가 지는 경우가 없을때
		ret = -1; //자신은 무조건 진다
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	Pre();

	for (int i = 0; i < 3; i++) {
		int input;
		cin >> input;

		b.push_back(input);
	}

	for (int t = 0; t < 5; t++) {
		cin >> k1 >> k2;

		int ret = Solve(k1, k2, 0);

		//A가 승자일때
		if (ret == 1) {
			result.push_back('A');
		}

		else {
			result.push_back('B');
		}
	}

	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << "\n";
	}

	return 0;
}