[백준/python3] 9657번 : 돌 게임 3

문제

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

9657번: 돌 게임 3

---

알고리즘 분류

• 다이나믹 프로그래밍
• 게임 이론

문제

돌 게임은 두 명이서 즐기는 재밌는 게임이다.
탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.
두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)

출력

상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.

예시

---

풀이 1

다이나믹 프로그래밍으로 이 문제를 풀 수 있다.

1. 가장 처음 판단이 가능한 경우에 대해서 확인한다.(1,3,4)
2. 다이나믹 프로그래밍으로 그 다음 경우를 확인한다. 그렇게 하여 N에 도달할 때까지 확인한다.

---

풀이 2

결과를 나열하다보면 규칙성을 찾을 수 있다. 하지만 꽤 많은 경우의 수를 확인해야 한다.

1 SK 2 CY 3 SK 4 SK 5 SK 6 SK 7 CY
8 SK 9 CY 10 SK 11 SK 12 SK 13 SK 14 CY
15 SK 16 CY 17  SK 18 SK 19 SK 20 SK 21 CY
22 SK 23 CY 24 SK 25 SK 26 SK 27 SK 28 CY

N % 7 == 2 or N % 7 == 0 의 경우에만 CY를 출력해야 한다는 걸 볼 수 있다.

---

소스코드 1

N = int(input())

dp = [False] * (N+1)

for i in range(1, N+1):
    if i-1 >= 0 and not dp[i-1]:
        dp[i] = True
    elif i-3 >= 0 and not dp[i-3]:
        dp[i] = True
    elif i-4 >= 0 and not dp[i-4]:
        dp[i] = True

if dp[N]:
    print("SK")
else:
    print("CY")

---

소스코드 2

N = int(input())

if N % 7 == 2 or N % 7 == 0:
    print("CY")
else:
    print("SK")

---