[백준 / BOJ] 9655 돌 게임 (Java)

문제

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

9655번: 돌 게임

N개의 돌이 주어지고, 두명의 플레이어(상근, 창영)가 있다. 각 플레이어는 번갈아가며 돌을 가져가는데 자신의 턴마다 1개 혹은 3개의 돌을 가져갈 수 있다. 플레이어는 매번 최선의 선택을 한다고 가정했을때, 상근이가 이기는지 창영이가 이기는지 구하는 문제다.

---

전형적인 게임이론 문제다.

dp배열을

dp[남아있는 돌의 수][turn] = 이긴 플레이어

와 같이 설정하고 자신이 이기는경우가 있다면 항상 그 경우를 선택하면 된다. 즉, 자신이 이기는 경우가 한번이라도 존재한다면, 절대로 지지 않는다.(매번 최선의 선택을 하기때문)

 

주요 소스코드

	private int pickStone(int remainStone, int turn){
		if(turn == 0) return nextTurn(turn);
		if(this.dp[remainStone][turn] != 0) return this.dp[remainStone][turn];
		for(int i = 0; i < this.pick.length; i++){
			if(remainStone - this.pick[i] < 0) continue;
			int winPlayer = this.pickStone(remainStone-this.pick[i], this.nextTurn(turn));
			if(winPlayer == turn) this.dp[remainStone][turn] = winPlayer;
		}
		if(this.dp[remainStone][turn] == 0) this.dp[remainStone][turn] = this.nextTurn(turn);
		return dp[remainStone][turn];
	}

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/9655%20%EB%8F%8C%20%EA%B2%8C%EC%9E%84/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃