BOJ 9655번 : 돌 게임 (Python/구현, DP/Silver 5)

9655번: 돌 게임

---

설명

돌 N개가 주어질 때, 두 사람(상근이와 창영)이 턴을 돌아가면서 돌을 가져간다.
돌을 1개 또는 3개 가져갈 수 있고, 마지막 돌을 가져가는 사람이 게임을 이기게 된다. (베스킨 라빈스 생각나네?)
게임은 상근이가 먼저 시작하며 두 사람이 완벽하게 게임을 한다고 가정하고, 이기는 사람을 출력한다.

풀이

1. 간단한 풀이

돌이 짝수일 경우 창영이가 무조건 이기는 게임이 되고, 홀수일 경우 상근이가 무조건 이기는 게임이 된다.

따라서 짝수일 때와 홀수일 때를 나누어 푼다.

 

2. 다이나믹 프로그래밍 알고리즘 적용

다른 풀이 참조(추후에 재풀이 후 설명 예정)

Solution

1. 간단 풀이

import sys
input = sys.stdin.readline

n = int(input()) #돌 개수

if n % 2 == 0: #짝수
    print('CY')
else: #홀수
    print('SK')

 

2. DP 풀이

import sys
input = sys.stdin.readline

n = int(input()) #돌 개수

dp = [0]*1001
dp[1], dp[2], dp[3] = 'SK', 'CY', 'SK'

for i in range(4, n+1):
    if dp[i-1] == 'CY' or dp[i-3] == 'CY':
        dp[i] = 'SK'
    else:
        dp[i] = 'CY'
        
if dp[n] == 'SK':
    print('SK')
else:
    print('CY')

---

👩‍💻 회고

처음에 풀이법이 도저히 생각나지 않아서 꼼수를 부렸다. 홀수와 짝수로 나눠서 계산해보니 필승법이 있었다는 걸 깨닫고 바로 풀었다. 그러나 이 문제는 다이나믹 프로그래밍 알고리즘으로도 풀 수 있었다. 사실 간단하게 풀기 전에 'dp로 풀어야 할 것 같은데..'라고 생각했었지만 dp에 아직 익숙해지지 않아서 다른 풀이를 참조했다. ㅜㅜ

dp 문제 중에서도 쉬운 편에 속하지만 아직 난... 많이 풀고나서 다시 풀어봐야겠다고 다짐.