[백준] 9655 돌 게임 - 동적계획법(Dynamic Programming, DP) + 게임이론(Game Theory) JAVA

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

9655번: 돌 게임

코드설명

게임이론 문제입니다.

 

각각 게이머들은 1개와 3개씩 가져올 수 있는데 이 값은 결국, 홀수라는 의미입니다.

두 게이머 둘다 홀수개의 돌을 가져올 수 있는데

이떄, 홀수개라면 처음에 가져간사람이 이기고, 

짝수개라면, 두번째로 가져간사람이 이깁니다.

 

이유는 두사람 합쳐서 무조건 짝수개의 돌밖에 가져가지 못하니 돌의 개수가 홀수라면,

먼저 가져간 사람에게 항상 돌은 1개가 남습니다.

 

또, 문제에서 이해해야하는점은,

만약 2개의 돌이 존재한다면, 이떄 3개의 돌, 즉 2개의 돌을 모두 가져가면서 게임을 이기는게 아닌, 딱 3개가 존재할떄만 돌을 가져올 수 있습니다. 해당 사항을 놓쳐서 코드2의 기저사례 처리에 어려움을 겪었습니다.

또 위와 같은 문제이해로, stone >= 4 로 처리하여 돌을 가져오는 것 또한 처리하는데 어려움이 있었습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	public static int T, N;
	public static int answer = 0;
	public static int[][] dp;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	
    	if(N % 2 == 1) {
    		System.out.println("SK");
    	}    	
    	if(N % 2 == 0) {
    		System.out.println("CY");
    	}

    }
   
}

코드 2

package Main;

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

public class Main {
    public static int N, T, M; 
    public static int answer = 0;
    public static int[] cache;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
        cache = new int[N + 1];
        Arrays.fill(cache, -2); // 초기값을 -2로 설정 (아직 계산되지 않음을 의미)
        String winner = (game(0, N) > 0) ? "SK" : "CY";
        System.out.println(winner);
	}
    
    
    //game(level, stones) : level%2 인 사람이 stones 개의 돌을 선공을 하여 돌게임을 헀을떄, 이긴다면 1을 반환하고, 진다면 -1을 반환한다.  
    public static int game(int level, int stones) {
    	if(stones == 1) {
    		//만약 선공인사람이 0번쨰 돌을 먹는다면, 후공이 이긴다는 의미이므로 -1 을 반환한다.
    		return (level % 2 == 0) ? 1 : -1;
    	}
    	
    	if(cache[stones] != -2) {
    		return cache[stones];
    	}
    	
    	int bestScore;
    	
    	//선공자 입장에서는 최대값이 이기는 것 이다.
    	if(level%2 == 0) {
    		bestScore = -2;
    		//stones >= 4 인경우만 보는 이유는, 돌이 4개이상이 아니라면, 애초에 돌을 선택할 수 없기 때문에, 이 선택지는 실제로 불가능합니다.
    		//그러므로, stones < 4 미만 이라면 이 선택지는 실제로 불가능하다는 의미로 -2 를 반환합니다.
    		//예시로, 만약 stones = 2인 상태로 처리한다면, 돌이 2개인상태에서 반드시 돌을 3개만 선택할 수 있으므로 애초에 이 선택지는 불가합니다.
    		bestScore = Math.max(game(level + 1, stones - 1), stones >= 4 ? game(level + 1, stones - 3) : -2);
    	}
    	//후공자 입장에서는 -1이 이기는 것 이다.
    	else {
    		bestScore = 2;
    		bestScore = Math.min(game(level + 1, stones - 1), stones >= 4 ? game(level + 1, stones - 3) : 2);
    	}
    	
    	return cache[stones] = bestScore;
    }
    
    
}