BOJ_2600_구슬게임 (Java)

[Gold IV] 구슬게임 - 2600

문제 링크

성능 요약

메모리: 15164 KB, 시간: 132 ms

분류

다이나믹 프로그래밍, 게임 이론

제출 일자

2025년 2월 15일 02:05:23

문제 설명

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

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

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

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

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

처음 두 통 속에 들어 있는 구슬의 수 k₁, k₂와 한 번에 꺼낼 수 있는 구슬의 수 b₁, b₂, b₃에 대한 제한조건은 다음과 같다.

• 1 ≤ b₁ < b₂ < b₃ ≤ 30
• 1 ≤ k₁, k₂ ≤500

입력

첫 줄에는 한번에 꺼낼 수 있는 구슬의 개수를 나타내는 세 개의 정수 b₁, b₂, b₃ 가 나타난다. 그 다음 5개의 각 줄에는 두 통속에 처음 담겨있는 구슬의 개수 k₁, k₂가 각각 표시되어 있다.

출력

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

문제풀이

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static int[] marble = new int[3];
    static boolean[][] dp;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_2600_구슬게임/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<3; i++) {
            marble[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(marble);
        dp = new boolean[501][501]; // A입장에서 false패배 true승리

        dp[0][0] = false;
        for(int i=0; i<501; i++) {
            for(int j=0; j<501; j++) {
                if(i < marble[0] && j < marble[0]){
                    dp[i][j] = false;
                    continue;
                }
                boolean canwin = false;

                // 왼쪽주머니 선택
                for(int k=0; k<3 && !canwin; k++){
                    if(i >= marble[k] && !dp[i-marble[k]][j]) canwin = true;
                }

                // 오른쪽주머니 선택
                for(int k=0; k<3 && !canwin; k++){
                    if(j >= marble[k] && !dp[i][j-marble[k]]) canwin = true;
                }

                dp[i][j] = canwin;
            }
        }

        for(int q=0; q<5; q++){
            st = new StringTokenizer(br.readLine());
            int k1 = Integer.parseInt(st.nextToken());
            int k2 = Integer.parseInt(st.nextToken());
            sb.append(dp[k1][k2] ? "A" : "B").append("\n");
        }
        System.out.println(sb);
        bw.flush();
        bw.close();
        br.close();
    }
}