백준 - 9655. 돌 게임 1

[백준] 9655. 돌 게임1

Link

문제

돌 게임은 상근이와 창영이가 하려는 게임이다.

돌 N개가 있고, 각 플레이어는 서로 턴을 번갈아가면서 돌을 가져간다 (상근이가 항상 먼저 시작한다).

이때 돌은 1개 또는 3개씩만 가져갈 수 있다.

마지막으로 돌을 가져가는 사람이 게임을 이긴다.

두 플레이어가 합리적으로 게임한다고 했을 때, 이기는 사람을 구하는 프로그램을 작성하라.

입력

첫째 줄에 N이 주어진다$(1<=N<=1000)$.

출력

상근이가 이기면 “SK”, 창영이가 이기면 “CY”를 출력하라.

풀이

게임이론 카테고리에 해당하는 알고리즘 문제이다.

문제에 나와있는대로 두 플레이는 합리적으로 자신의 이익을 극대화하는 방향, 즉 승리하기 위해 이성적인 의사결정을 한다는 것이 보장되어있다.

다시 말하면, 참가자들은 돌을 1개 또는 3개만 가져갈 수 있는 룰을 지키면서 게임을 진행하고, 결과적으로 합리적으로 게임을 하기 때문에 항상 “최소“의 턴으로 게임이 끝나게 된다.

위 사항들을 명심하면서 문제를 풀어보자.

우선 몇 가지 작은 수를 대입하여 누가 이기게 되는지 나열해보자.

돌 개수 (N)	1	2	3	4	5	6	7	8
승리자(SK or CY)	SK	CY	SK	CY	SK	CY	SK	CY

1번째 방법

N의 범위가 1부터 1000이기 때문에 아직 모든 돌의 개수에 대해서도 성립하는지 확신할 수 없으나,

승리자는 돌의 개수가 홀수인지, 짝수인지에 따라 정해지는 것으로 보인다.

하지만 위 규칙이 더 큰 수에서도 성립한다는 보장이 있는가?

사실 이 부분은 쉽게 증명이 가능하다.

상근이나 창영이가 각자의 턴에 1개을 가져가든, 3개를 가져가든, 상근이 턴에는 무조건 홀수, 창영이 턴에는 무조건 짝수개를 가져가게 됨으로 N이 몇이든 항상 성립한다.

위 해결책을 코드로 옮기면 아래와 같다.

N = int(input())

if N % 2 == 1:	# Odd Number
    print("SK")
else:			# Even Number
    print("CY")

2번째 방법

이 문제는 게임이 워낙 단순하기 때문에 위 1번 방법과 같은 간단한 방법으로 풀 수가 있다.

하지만 이번에는 수고스럽더라도, 게임 진행 방식, 규칙에 의거하여 해결 방법을 찾아보자.

• 참가자들은 승리하기 위해 이성적인 의사결정을 한다는 것이 보장되어있다.
• 참가자들은 각자의 턴에 1개 또는 3개의 돌을 가져간다.
• 마지막으로 돌을 가져가는 사람, 즉 게임이 끝나는 마지막 턴에 돌을 가져가는 사람이 게임을 승리한다.
  • 상근이가 항상 먼저 시작하기 때문에 상근이는 1,3,5,7..턴, 창영이는 2,4,6,8..턴에 돌을 가져간다.

위 조건들을 보면, 홀수 턴에 게임이 끝나면 상근이, 짝수 턴에 게임이 끝나면 창영이가 승리하게 된다.

즉, 돌의 개수에 따른 게임이 끝나는 최소 턴 횟수를 알면 누가 이겼는지 결정이 가능하다.

그렇다면 최소 턴 횟수는 어떻게 구할 수 있을까?

돌 개수 (N)	1	2	3	4	5	6	7	8
최소 턴 횟수	1	2	1	2	3	2	3	4

N이 1부터 8일 때 까지의 최소 턴 횟수를 보면 아래와 같은 규칙이 보인다.

• N=4 일 때 최소 턴 횟수는 N=1 일 때와 N=3일 때 최소 턴 횟수에 1을 더한 것과 같다.
• N=6 일 떄 최소 턴 횟수는 N=3 일 때 최소 턴 횟수에 1을 더한 것과 같다.
• N=8 일 때 최소 턴 횟수는 N=7 일 때와 N=5일 때 최소 턴 횟수에 1을 더한 것과 같다.

정리하면, N에 따른 최소 턴 횟수는 (N-1) 또는 (N-3) 일 때 최소 턴 횟수에 1을 더한 것이 되지만, N=6 일 때 처럼 항상 (N-1)과 (N-3)일 때 최소 턴 횟수가 같진 않다.

하지만 참가자들은 승리하기 위해 항상 이성적인 의사결정을 한다는, 즉 최소 턴 횟수로 게임이 끝난다는 전제가 있기 때문에,

(N-1)과 (N-3) 일 때의 최소 턴 횟수중에 더 작은 턴 횟수에 1을 더한 값이 N 일 때의 최소 턴 횟수가 된다.

이를 수식화하면 아래와 같다. \(dp[N] = Min(dp[N-1] + 1,\ dp[N-3] + 1)\) 반가운 형태의 수식이다.

그렇다. 크고 어려운 문제가 있으면 그것을 먼저 잘게 나누어서 해결한 뒤 처리하여 나중에 전체의 답을 구하는, 이 과정에서 Memorization이 사용되는 다이나믹 프로그래밍으로 이 문제를 풀 수 있다.

N = int(input())  
dp = [0] * (N+1)	# 혼란을 방지하기 위해 index 0은 비워둠
dp[1] = 1
dp[2] = 2
dp[3] = 1

for n in range(4, N+1):
    dp[n] = min(dp[n-1], dp[n-3]) + 1
 
if dp[N] % 2 == 1:
    print('SK')
else:
    print('CY')