[백준] 2600 - 구슬게임

[문제링크]

2600번: 구슬게임

 

0. 두 상자에 x,y개의 구슬이 있고, b1,b2,b3 중 하나만큼 구슬을 꺼낼 수 있을때, 최종 승자를 찾는 문제

 

1. (x, y)에서 시작해 b1, b2, b3를 빼는 경우의 수 전체를 고려했을때, 단 하나라도 승리하는 경우가 있다면 승리한다

 

2. 반대로, 모든 경우의 수가 패배라면, 패배한다

 

3. 선제공격이 이기는 경우를 true, 지는 경우를 false로 둔다

 

4. 최소 선택 단위인 b1보다 구슬의 수가 적다면 선택할수 없으므로 패배한다, 이를 기초로 DP 진행

 

5. 선공인 A가 어떠한 선택을 하여 구슬 상태가 (x', y')로 변했는데, DP[x'][y']가 선공 승리인 상태라면, A는 패배한다

• (x', y')상태에서는 턴이 넘어가 B가 선공이 되기 때문
• 즉, DP[x'][y']로 진행할 경우 현재 상태인 DP[x][y]에서의 결과는 !DP[x'][y']가 된다

 

6. DP 테이블이 완성되면 구한 결과 출력

 

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

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int b1 = pint(st.nextToken());
		int b2 = pint(st.nextToken());
		int b3 = pint(st.nextToken());
		
		boolean[][]dp = new boolean[501][501];
		
		for (int i = 0; i < dp.length; i++) {
			for (int j = 0; j < dp.length; j++) {
				if(i>=b1&&j>=b1) {
					//어떤 선택을 하더라도 상대 승리
					if(dp[i-b1][j] && dp[i][j-b1])dp[i][j]=false;
					//내가 이기는 선택지가 존재
					else dp[i][j]=true;
				}
				else if(i>=b1)dp[i][j]=!dp[i-b1][j];
				else if(j>=b1)dp[i][j]=!dp[i][j-b1];

				//위에서 결정되지 않았을 경우에만
				if(!dp[i][j]) {
					if(i>=b2&&j>=b2) {
						//어떤 선택을 하더라도 상대 승리
						if(dp[i-b2][j] && dp[i][j-b2])dp[i][j]=false;
						//내가 이기는 선택지가 존재
						else dp[i][j]=true;
					}
					else if(i>=b2)dp[i][j]=!dp[i-b2][j];
					else if(j>=b2)dp[i][j]=!dp[i][j-b2];
				}
				
				//위에서 결정되지 않았을 경우에만
				if(!dp[i][j]) {
					if(i>=b3&&j>=b3) {
						//어떤 선택을 하더라도 상대 승리
						if(dp[i-b3][j] && dp[i][j-b3])dp[i][j]=false;
						//내가 이기는 선택지가 존재
						else dp[i][j]=true;
					}
					else if(i>=b3)dp[i][j]=!dp[i-b3][j];
					else if(j>=b3)dp[i][j]=!dp[i][j-b3];
				}
			}
		}
		 
		for (int i = 0; i < 5; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int k1 = pint(st.nextToken());
			int k2 = pint(st.nextToken());
			
			System.out.println(dp[k1][k2]?'A':'B');
			
		}
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면