백준[ 9657 | Python ] 돌 게임 3

문제

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

풀이

먼저 dp테이블에 각 돌이 주어졌을 때 이기는 사람의 이름을 적어둔다.
돌이 4개인 경우까지 필요한 이유는 돌을 최대 4개 까지 빼줄 수 있기 때문이다.

다음으로 dp를 수행한다. 선수는 상근이므로 창영이가 두는 경우는 배제하고, 상근이가 선수였지만 졌던 돌의 개수만을 따라간다.
돌을 1, 3, 4개를 가져갈 동안 상근이가 졌던 경기가 없었다면 창영이가 승자가 되고, 돌을 1, 3, 4개 가져갈 동안
상근이가 졌던 경우가 한 번이라도 있다면 상근이가 승자가 된다.

위에서 상근이가 지는 경우만을 따르는 이유를 예시로 설명하자면,
돌이 6개가 주어진 경우, 상근이가 1개의 돌을 가져간다고 했을 때
창영이가 5개의 돌로 시작하는 경우와 같다.
이 때 상근이가 이전에 5개의 돌이 주어졌을 때 승리 했기 때문에 창영이도 승리한다.
즉, 내가 먼저 가져갈 수 있어서 승리했던 게임은 상대가 먼저가져 가는 경우에 똑같이 승리하기 때문이다.
따라서 상근이는 항상 창영이가 불리할만한 수를 골라야한다. 불리할만한 수가 없다면 상근이는 진다.

n = int(input())
dp = [0]*1001
dp[1],dp[2],dp[3],dp[4] = "SK","CY","SK","SK"
stones = [1,3,4]


for i in range(5,n+1):
    for s in stones:
        if dp[i-s] == "CY":
            dp[i] = "SK"    
            break
        dp[i] = "CY"

print(dp[n])

생각 & 정리

처음에는 돌의 개수로 dp테이블을 만들어 가려고 했다.
하지만 완벽하게 게임을 한 경우를 일일이 체크해야 하기 때문에 불가능하다고 느꼈다.
이런 저런 고민을 하다가 결국에 다른 블로그를 참고했는데, 내 마음에 쏙 드는 답 들을 찾기 힘들었다.
결국 오기가 생겨서 해결했는데, 내 생각을 넓히는데 도움이 된 문제 같다.
새로운 분류를 만났을 때 한번쯤은 더 골똘히 생각하는 시간을 가지면 좋은 것 같다.