BOJ 2600

구슬게임 

 

두 사람 A와 B가 번갈아 가면서 두 개의 구슬 통에서 몇 개씩의 구슬을 꺼내는 게임을 한다.

한번에 한 사람이 한 통에서 꺼낼 수 있는 구슬의 개수는 세 가지 뿐이다. 그리고 구슬을 꺼낼 경우 두 개의 구슬 통 중에서 하나를 마음대로 선택해서 그 안에서만 꺼낼 수 있다. 즉 두 개의 통 모두에서 동시에 몇 개씩 꺼낼 수는 없다.

게임은 항상 A가 먼저하고 그 다음 B, 그 다음 A 순으로 번갈아가면서 진행된다. 그리고 자신의 차례가 되었을 때에 정해진 규칙대로 구슬을 꺼낼 수 없는 사람이 게임에서 지게 되고, 상대방은 승리하게 된다.

예를 들어 한번에 꺼낼 수 있는 구슬의 개수를 1개, 3개, 또는 4개라고 하자. 만일 두 개의 구슬 통에 각각 4개, 1개의 구슬이 있다고 하면 처음 선택을 하게 되는 A가 이긴다. 그러나 만일 두 통속의 구슬이 각각 5개, 5개라면 B가 이긴다.

즉 한번에 꺼낼 수 있는 구슬 개수인 b1, b2, b3가 주어지고, 두 구슬 통 속에 들어있는 구슬의 수인 k1, k2이 정해지면, 이러한 b1, b2, b3와 k1, k2에 따라서 승패는 결정된다. 문제는 주어진 b1, b2, b3와 k1, k2에 대하여 A, B중 누가 승자인지를 결정하는 것이다.

처음 두 통 속에 들어 있는 구슬의 수 k1, k2와 한 번에 꺼낼 수 있는 구슬의 수 b1, b2, b3에 대한 제한조건은 다음과 같다.

• 1 ≤ b1 < b2 < b3 ≤ 30 
• 1 ≤ k1, k2 ≤500

입력

첫 줄에는 한번에 꺼낼 수 있는 구슬의 개수를 나타내는 세 개의 정수 b1, b2, b3 가 나타난다. 그 다음 5개의 각 줄에는 두 통속에 처음 담겨있는 구슬의 개수 k1, k2가 각각 표시되어 있다.

출력

각 5개의 k1, k2 경우에 대하여 그에 대응되는 승자(A 또는 B)를 각각 한 줄에 하나씩 차례대로 다섯 개를 출력해야 한다.

dp문제

A가 결국 한방만 이기게 하면 됌. 이기는 단 하나의 경우가 있다면 그 경우로 가서 이기면 되니까.

A가 처음부터 구슬 꺼내는 단계에 따라 탑다운 방식으로 진행

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {
    static int[][][] dp = new int[2][501][501];
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int [] value = new int[3];

        for(int i =0; i<3; i++) value[i]= Integer.parseInt(st.nextToken());
        for(int a=0; a<2; a++)
            for(int i=0;i<=500; i++)
                for(int j =0; j<=500; j++)
                    dp[a][i][j]=-1;

        for(int i =0; i<5; i++){
            st = new StringTokenizer(br.readLine());
            int f = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());

            if(game(value,f,s,false)==1)System.out.println("A");
            else System.out.println("B");
        }
    }
    private static int game(int[] value, int f, int s, boolean flag){
        int AorB=0;
        if(flag ==true)AorB=1;

        if(dp[AorB][f][s]!=-1)return dp[AorB][f][s];

        for(int i=0; i<3; i++)
            if(f-value[i]>=0 && game(value,f-value[i],s,!flag)==0)return dp[AorB][f][s]=1;

        for(int i=0; i<3; i++)
            if(s-value[i]>=0 && game(value,f,s-value[i],!flag)==0)return dp[AorB][f][s]=1;

        //맨 밑에 depth 까지 내려와봄
        //여기 도달 했다는 것은 A나B가 더이상은 구슬을 선택할 수 없다는 뜻임==졌다는 뜻임
        //그래서 A또는 B의 구슬 상태 f s에는 졌다는 도장을 쾅 찍는 것임
        //그리고 여기서 0이 리턴되기때문에 이전단계로 올라가서 상대는 이겼다는 걸 리턴해줌
        //그러면 또 그위로 올라가서 다른 선택지로 가봄 또 누군가는 이기고 지고의 도장을 받고 상위로 졌다 이겼다를 알려줌
        //그럼 첫번쨰로 돌아와서 앞선 판에서 졌다는 게 하나라도 올라온다면
        //만약 game (value, 4, 1, false) 이상태에서 함수로 들어왔는데
        //return false 가 다음 단계에서 올라온다면 현 단계는 true 가 되고 그건 이겼다는 것을 의미함.
        //다시 올라가서 모든 첫 시작으로 파생된 모든 선택에 도장을 찍음
        return dp[AorB][f][s]=0;
    }

}