백준 9657 돌 게임 3

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

9657번: 돌 게임 3

처음 봤을 때도 어려웠는데, 다시봐도 쉽지 않다...

이 문제도 결국에는 처음 몇가지를 하나씩 써내려나가는게 도움이 된다. 그로 인해 어떠한 규칙성을 파악할 가능성이 있기 때문이다.

 

돌을 1, 3, 4개씩 가져갈 수 있으므로, 돌이 1, 3, 4개씩 처음에 주어진 경우는 당연히 상근이가 무조건 이긴다. (다 가져가면 되니깐)

 

돌이 5개 주어진 경우를 생각해보자. 

돌을 상근이가 4개 갖고 가면 그 다음 창영이가 1개를 들고가서 지게된다! 상근이가 1개 들고 갔어도 창영이가 4개 들고 가버리면 패배하고만다. 하지만 3개만 들고 갔다면 상근이가 이길 수 있다. 문제에서 말하는 '두 사람이 완벽하게 게임을 했을 때'의 의미가 바로 이러한 상황에서 상근이가 3개만 들고 간다는 것을 의미한다. 상근이는 자신이 이기기 위해 3개만 들고 가는 것이다. 상근이가 먼저 턴을 가지고 있으니.

 

그렇다면 이 말은 처음에 주어진 돌 5개에서 가져갈 수 있는 옵션 (1, 3, 4)을 하나씩 대어보고 이길 수 있는 경우가 있다면 그것을 택하면 된다는 것이 된다. 이번에도 결국 다이나믹 프로그래밍의 방식이다 (매 정점에서 최적의 값을 저장하기 때문에). 매 정점에서 가져갈 수 있는 돌만큼의 이전 정점 값을 확인하여 이기는 경우가 있다면 그것을 기록하는 것이다.

 

다이나믹 프로그래밍의 점화식을 세우는 일은 쉽지 않다. 그런데 여러 문제를 풀어보다보면 몇가지 유형이 보이는 경우가 있는데, (물론 유형만을 기억하는 것은 크게 도움이 되지 않는다. 어떤 유형을 언제 사용할지 판단하는 것부터 쉽지 않기에...)

• 바로 이전 정점에 근거하여 현재 정점의 답을 구하는 방식
• 이전 몇 개의 연속된 정점 몇개를 확인하여 답을 구하는 방식
• 현재 정점에서 특정한 연산에 의해 구한 이전 정점을 확인하여 현재 정점의 답을 구하는 방식
• 현재 정점에서 문제에서 주어지는 경우의 수만큼의 이전 정점을 확인하는 방식

등등이 있다. 사실 이외에도 굉장히 많다. 그냥 문제의 요구사항에 따라 얼마든지 무한한 방식이 나올 수 있다. 이번 문제는 가져갈 수 있는 돌들 만큼의 이전 정점을 확인하는 방식이 되겠다.

 

아래의 그림을 보자.

글에서 설명한 바와 같이, DP[5]를 예시로 들어보면 DP[5]에서 3가지 (가져갈 수 있는 경우의 수) 이전 경우를 모두 살펴본다. 

DP[1], DP[2], DP[4]를 보게 되는데 이중에 DP[2]가 CY이다. 즉 창영이 이기는 경우이다. 그렇다면 DP[5]에서 상근이가 승리할 수 있다.

뭔가 논리가 완벽해보이지 않을 수 있다. 여기서 위의 표가 의미하는 것을 한번 더 생각해보자. 가장 핵심이다. 필자도 이 부분에 대한 확실한 이해를 위해 상당히 애를 먹었다.

표에서 SK라고 쓴것은 상근의 이니셜이지만 사실 '먼저 둔 사람'을 의미하고, 'CY'은 나중에 둔 사람을 의미한다!

즉 DP[2]에서 CY이란 것은 돌이 2개 있을 때는 먼저 둔 사람이 진다 (나중에 둔 사람이 이긴다)를 의미한다.

 

다시 설명하면, DP[5]일 때는 상근이가 먼저 두는 상황이고, 아직 이길지 어떨지 몰라서 3가지 이전 상황을 살펴보게 된다.

3개를 골라서 DP[2]일 때는 창영의 턴인데, 이것을 바꾸어 생각하면 상근이가 나중에 두는 상황이 된다. 5에서 3을 빼서 2가 되었으니 창영의 턴이 온 것인데, 이것을 돌이 애초에 2개 있었고, 창영이가 먼저 선택하는 상황으로 이해한다는 것이다. 그렇다면 위의 그림에서 DP[2]='나중에 둔 사람의 승리'이므로 상근이의 승리가 되는 것이다!

돌 5개로 시작하는 게임에서 처음에 돌을 3개 가지고 가버리면 속절없이 처음에 두는 사람이 승리하는 것이다.

 

한번 더 예를 들어 돌이 8개 있는 경우를 생각해보자.

DP[7], DP[5], DP[4]를 살펴봐야 하는데, DP[5]와 DP[4]는 SK이다. 이 말은 사실 창영의 승리를 뜻한다. 5나 4의 상황에서는 창영이 먼저 두는 상황이기 때문이다. 하지만 DP[7]은 나중에 두는 사람이 승리하는 상황이다. 그래서 이길수도 있고 질수도 있지만, 문제에서 완벽한 게임을 한다고 했으므로 상근이는 이 상황을 선택하여 게임에서 승리하는 것이다.

 

이번에는 풀어서 생각해보자.

돌 8개가 있을 때, 

상근이가 3개를 처음에 가져오면, 그 다음에 창영이가 3개를 챙겨서 상근이가 진다. (표의 내용과 같다.)

상근이가 4개를 가져오면, 창영이가 4개를 모두 챙겨서 상근이가 또 진다. (이것도 표의 내용과 같다. DP[4]=SK이기 때문)

다시 말하지만 DP[4]=SK 는 상근이가 이기는게 아니고 턴을 먼저 가진 사람이 승리한다를 의미한다. DP[4]인 상황에서 창영의 턴이므로 창영의 승리. (애초에 그림에서 더 잘 표현했어야 하는건데 죄송합니다.)

이제 마지막 케이스. 상근이가 1개를 가져오면, 7개가 된다. 이제 창영이의 턴인데, 창영이가 3개나 4개를 챙기면 창영이가 진다. 그래서 창영이는 1개를 가져올 수 밖에 없다. 그것이 그 상황에서의 창영이의 최선의 선택이 된다. (사실 이렇게 일일이 확인하지 않으려고 다이나믹 프로그래밍을 통해 DP[7]=CY이라고 기록해두는 것이다. 이것이 바로 다이나믹 프로그래밍의 가장 중요한 핵심이기도 하다) 그럼 이제 6개 된다. 여기서 상근이는 4개를 가져오면 무조건 이길 수 있으니 그 선택을 하게된다. 즉 창영이는 여지없이 패배할 수 밖에 없다!

 

DP[i]에서 게임의 결과가 저장되어 있어도 다른 i값의 게임을 한다면 선택의 경로가 바뀌지 않을까? 하는 생각으로 인해 상당히 이해하기 까다로웠다. 설명글이 미래의 나에게 그리고 이 글을 보시는 분들에게 조금이라도 도움이 되길 바란다.

 

<주요 내용>

다이나믹 프로그래밍

 

<코드>

Python

n, stones = int(input()), [1, 3, 4]
dp = [0 for _ in range(n+1)]
for i in range(n+1):
    flag = False
    for stone in stones:
        if i-stone < 0:break
        if not (i-stone) or dp[i-stone]:
            flag = True
            break
    if not flag:
        dp[i] = 1
print('CY' if dp[n] else 'SK')