[DP]BOJ 2600_구슬게임

문제 링크 : www.acmicpc.net/problem/2600

2600번: 구슬게임

 

개인적으로는 DP문제가 어려운 이유를 느낄 수 있었던 문제이다.

이 문제는 복잡하게 생각할수록 풀기 어렵고, DP의 개념 중 하나인 분할 정복을 잘 생각한다면 쉽게 풀 수 있는 문제이다.

 

양쪽 통에 구슬이 각각 x개, y개 들어있을 때, 현재 구슬을 꺼내야 하는 플레이어가 이기는 경우를 생각해 보자.

플레이어는 여러 가지 수를 둘 수 있다. 문제에서 제시된 예제의 경우만 해도 최대 6가지 행동을 취할 수 있다.

플레이어가 구슬을 꺼낸 후 통의 구슬 개수를 각각 x2, y2라 하면, 이제는 상대 플레이어가 여러 수를 둘 수 있다.

이렇게 각 플레이어들이 구슬을 꺼내다 보면, 게임을 끝낼 수 있는 시점이 온다.

예제에서 게임이 끝나는 경우

예제에서 게임이 끝나는 경우는 다음과 같다. (구슬을 꺼내기 전의 통 상태를 나타낸 것임)

최초의 통 상태와 상관없이, 각 플레이어가 구슬을 꺼내다 보면

게임이 끝나는 순간에는 반드시 위 그림에 나타난 상태 중 하나에서 끝나게 된다.

이는 전개도를 그려보면 더욱 확실히 알 수 있다. 

 

어떠한 상태에서도, A가 이길수 있는 길(상태)로 갈 수만 있다면, A는 이길 수 있는 것이다. (이 부분이 제일 어려웠다)

만약 A가 어떤 수를 뒀을 때, 그로부터 파생되는 모든 경우에서 A가 진다면, A는 그것을 선택하지 않을 것이기 때문이다.

(이는 B도 마찬가지이다.)

 

예제에서는 A가 꺼낼 차례가 되었을 때 통의 상태를 (1, 0) 또는 (0, 1)로만 만들 수 있다면 반드시 이길 수 있다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <memory.h>
 
using namespace std;
 
int b[3];
int dp[501][501][2] = { -1, };
 
int winner(int f, int s, bool p) {
    //Top-Down 방식으로 DP 사용
    //f, s는 양쪽 통에 남은 구슬의 갯수를 의미, p는 구슬을 가져가야 하는 플레이어를 의미 (A : false, B : true)
    //DP의 값은 승리할 수 있는지를 나타냄
    if (dp[f][s][p] != -1) return dp[f][s][p];
 
    for (int i = 0; i < 3; i++) 
        if (b[i] <= f && !winner(f - b[i], s, !p)) return dp[f][s][p] = true;
 
    for (int i = 0; i < 3; i++) 
        if (b[i] <= s && !winner(f, s - b[i], !p)) return dp[f][s][p] = true;
 
    return dp[f][s][p] = false;
}
 
int main() {
    for (int i = 0; i < 3; i++)
        scanf("%d", b + i);
 
    for (int i = 0; i < 5; i++) {
        memset(dp, -1, sizeof(dp));
        int first, second;
        scanf("%d %d", &first, &second);
        if (winner(first, second, false)) printf("A\n");
        else printf("B\n");
    }
 
    return 0;
}