[python] 백준 9657 - 돌 게임3

출처 : 백준, https://www.acmicpc.net/problem/9657

9657번: 돌 게임 3

 

 

먼저, 생각해야 할 부분

 

1. DP 문제이다.

     규칙을 찾기 위해 한 단계 거슬러가서 생각해보자.

 

---

 

풀이

 

n = int(input())

FIRST_START = 1
LAST_START = 2

winner = [FIRST_START for _ in range(n+1)]
try:
  winner[2] = LAST_START
except:
  pass

for i in range(5, n+1):
  if LAST_START in [winner[i-4], winner[i-3], winner[i-1]]:
    winner[i] = FIRST_START
  else:
    winner[i] = LAST_START

print('CY' if winner[n] == LAST_START else 'SK')

 

돌을 가져올 수 있는 방법은 1, 3, 4개이다.

만약 돌이 n개 있다면 한 단계만 거슬러 가보면 n-1개, n-3개, n-4개의 돌이 있다고 생각할 수 있을 것이다.

이를 생각하고 1개씩 차근차근 살펴보자.

 

돌 개수	1	2	3	4	5	6	7	8	9
마지막 돌	선	후	선	선	선	선	후	선	후

(선 : 먼저 시작하는 사람, 후 : 나중에 시작하는 사람)

 

돌이 1개 있다면, SK가 먼저 시작하므로 1개를 가져가 SK가 이길 것이다.

돌이 2개 있다면, 인당 1개씩 밖에 가져갈 수 없으므로 마지막 1개를 가져가는 CY가 이긴다.

3이라면 처음부터 3개를 가져가면 되므로 SK가 이긴다.

4의 경우도 처음부터 4개를 가져가면 되므로 SK가 이긴다.

 

이제 돌이 5개이다. 먼저 플레이하는 SK 입장에서 생각을 해보자. 

SK는 돌을 1개, 3개, 4개를 가져갈 수 있다.

 

만약 돌을 1개 가져간다면 이제 판 위에는 돌이 4개가 남아있다.

위 표에 따르면 돌이 4개 일 경우에 먼저 시작하는 사람이 마지막 돌을 가져가므로 돌이 4개 일 때 시작하는 CY가 승리한다.

 

만약 돌을 3개 가져간다면 판 위에는 돌이 2개가 남아있고, 

위 표에 따르면 판 위에 돌이 2개 있을 경우에는 나중에 시작하는 사람이 마지막 돌을 가져가 승리한다.

즉, CY가 가져가고 다시 턴이 돌아오는 SK가 승리한다.

만약 돌을 4개 가져간다면 판 위에는 돌이 1개 남아있고,

위 표에 따르면 판 위에 돌이 1개 있을 경우에는 먼저 시작하는 사람이 마지막 돌을 가져가므로 CY가 승리한다.

플레이어들은 완벽하게 플레이하므로, 5개의 돌이 있다면, SK는 자신이 이길 수 있도록 3개를 가져갈 것이다.

즉, n-1, n-3, n-4 중에 한 번이라도 늦게 돌을 가져가는 사람이 승리하는 경우가 있다면 승자는 SK이다.

이를 코드로 나타내면 다음과 같다.

 

  if LAST_START in [winner[i-4], winner[i-3], winner[i-1]]:
    winner[i] = FIRST_START
  else:
    winner[i] = LAST_START

 

n-1, n-3, n-4개의 돌이 있을 때, 승자에 대하여 한 번이라도 CY가 있다면 SK가, 셋 모두 SK라면 CY가 된다.

 

---

시간 복잡도

O(N)

 

알게 된 점

 

-

 

고찰

 

이전 돌 게임 문제들은 짝수임을 이용해서 나머지로 그냥 풀었는데

이제야 문제 의도에 맞게 푼 게 아닐까 하는 생각이 든다...ㅎㅎ

 

Github

9657 - 돌 게임 3