백준 25949 Jar Game

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

25949번: Jar Game

 

풀이 

0. 핵심 아이디어

 

DP를 다음과 같이 정의합니다.

 

DP[t][a][b][c]

 

t번째 턴이고

항아리1에 a개의 조약돌이 있고

항아리2에 b개의 조약돌이 있고

항아리3에 c개의 조약돌이 있는 상태에서

F가 가질 수 있는 최대의 조약돌의 갯수

 

 

해당 DP식으로 유추할 수 있는 점화식의 수도 코드는 다음과 같습니다.

 

"F = DP(1,a,b,c)"의 값을 구하고

"S = a+b+c - F"라고 할때

 

F > S이면

F를 출력

 

F < S이면

S를 출력

 

F = S이면

D를 출력하면됩니다.

 

코드

#include <bits/stdc++.h>

#pragma warning(disable:4996)

using namespace std;

#define endl "\n"
#define int long long
#define float long double

const float INF = 1e10;
const int Dic[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };

//////////////////////////////////////////////////////////////////////// 

int DP[40][101][101][101];
int Dp(int pT, int pA, int pB, int pC)
{
	int& ref = DP[pT][pA][pB][pC];

	if (ref != -1)
		return ref;

	int gA = min(pT, pA);
	int gB = min(pT, pB);
	int gC = min(pT, pC);

	if (pA == 0 && pA == pB && pB == pC)
	{
		ref = 0;
	}
	else if (pT % 2 == 1) //F의 차례
	{
		ref = 0;
		if (gA > 0)ref = max(ref, Dp(pT + 1, pA - gA, pB, pC) + gA);
		if (gB > 0)ref = max(ref, Dp(pT + 1, pA, pB - gB, pC) + gB);
		if (gC > 0)ref = max(ref, Dp(pT + 1, pA, pB, pC - gC) + gC);
	}
	else //S의 차례
	{
		ref = INF;
		if (gA > 0)ref = min(ref, Dp(pT + 1, pA - gA, pB, pC));
		if (gB > 0)ref = min(ref, Dp(pT + 1, pA, pB - gB, pC));
		if (gC > 0)ref = min(ref, Dp(pT + 1, pA, pB, pC - gC));
	}
	return ref;
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	for (int i = 0; i < 40; i++)
		for (int j = 0; j < 101; j++)
			for (int k = 0; k < 101; k++)
				for (int l = 0; l < 101; l++)
					DP[i][j][k][l] = -1;

	int a, b, c;
	std::cin >> a >> b >> c;

	int F = Dp(1, a, b, c);
	int S = a + b + c - F;

	if (F == S)
		std::cout << "D" << endl;
	else if (F > S)
		std::cout << "F" << endl;
	else
		std::cout << "S" << endl;
}