[solve.ac 실버2] 9658_돌 게임 4 (파이썬, DP)

제한 사항

문제

돌 게임은 두 명이서 즐기는 재밌는 게임이다.

탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 지게 된다.

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

입력

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

출력

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

예제

---

나의 풀이

이 문제는 모든 경우를 확인하는 완전 탐색보다는 DP로 풀이하는 것이 훨씬 효율적이다.

DP 테이블의 i 번째 인덱스에 저장될 값은 i개의 돌이 있을 때 먼저 시작한 사람이 이길 수 있는지 없는지 여부이다.

예를 들어

돌이 한 개 있을 때:

먼저 시작한 사람이 항상 이긴다

돌이 두 개 있을 때:

먼저 시작한 사람이 항상 진다

돌이 세 개 있을 때:

먼저 시작한 사람이 이긴다. (3개를 한 번에 가져가면 질 수 있지만 1개를 가져가면 이긴다)

돌이 네 개 있을 때:

먼저 시작한 사람이 이긴다. (4개를 한 번에 가져가면 질 수 있지만 1개나 3개를 가져가면 이긴다)

이를 d 리스트에 담으면 d = [ _, True, False, True, Ture] 로 초기화 될 수 있다. (0번 인덱스는 어떤 값이 와도 상관 없다)

 

그러나 돌이 5개 있을 때는 이길 수도 있고, 질 수도 있다.

먼저 시작한 사람이 1개를 가져가면 4개가 남고, 4개가 남은 경우엔 상대 편이 이긴다.

4개가 남은 경우 상대가 왜 이기냐면 위에서 돌이 네 개 있을 때 먼저 시작한 사람이 이긴다고 했는데 4개가 남은 시점에 돌을 가져가는 사람이 나중에 시작한 사람이기 때문에 나중에 시작한 사람이 이기게 되는 것이다.

먼저 시작한 사람이 3개를 가져가면 2개가 남고, 2개가 남은 경우에도 상대 편이 이긴다.

하지만 먼저 시작한 사람이 4개를 가져가면 1개가 남고, 이 때는 먼저 시작한 사람이 이긴다.

이럴 때는 이긴다고 판단한다. 왜냐하면 문제에서 완벽하게 게임을 했다는 조건이 있기 때문에 이길 수 있는 방법이 있다면 이기는 방법을 선택해야 한다.

 

이를 일반화하면 현재 돌이 i개 일 때를 확인한다면 d[i - 1]과 d[i - 3]과 d[i - 4]가 모두 True인 경우엔 먼저 시작한 사람이 절대 이길 수 없는 경우이고, 그 외에는 이길 수 있는 방법이 존재한다는 말이다.

이를 조건문으로 판별할 수도 있지만 우리는 비트 연산자를 사용할 수 있다. ( '|' 나 '&' 같은 것)

코드로 작성하면 다음과 같다.

전체 코드

d = [True, False, True, False, True]

def answer(index):
    print('SK') if d[index] else print('CY')

def solution():
    n = int(input())
    for i in range(5, n + 1):
        d.append(not (d[i-1] & d[i-3] and d[i-4]))
    answer(n)

solution()

채점 결과