[Python] 백준 9655 돌 게임 | DP

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

9655번: 돌 게임

 

 

문제 해결 포인트

- DP(다이나믹 프로그래밍)

- 기록을 위한 dp 배열 : 0은 SK, 1은 CY를 의미

 

- N이 1일 때 : SK

   N이 2일 때 : SK -> CY

   N이 3일 때 : SK 또는 SK -> CY -> SK  이므로 결론적으로 SK

   N이 4일 때 : 1일 때 결과와 다른 사람 또는 3일 때 결과와 다른 사람, 결론적으로 CY

   ......

 

- 점화식

   N이 4이상일 때, a_i = (a_i-1 + 1) % 2 또는 a_i = (a_i-3 + 1) % 2

 

 

작성 코드

N = int(input())
dp = [0]*1001

# SK == 0, CY == 1
dp[1] = 0
dp[2] = 1
dp[3] = 0

for i in range(4, N+1):
    dp[i] = (dp[i-1] + 1) % 2  # 또는 dp[i] = (dp[i-3] + 1) % 2

print('SK' if dp[N] == 0 else 'CY')

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚