[문제]
$N$ 개의 바둑돌이 담긴 항아리가 있다. 이 항아리를 두고 $F$ 와 $S$ , 이 두 사람이 게임을 한다. 게임은 자신의 차례가 왔을 때 항아리에서 3가지 선택 $s_1$, $s_2$, $s_3$ 중 하나를 선택해서 $s_i(i=1,2,3)$개의 돌을 꺼낼 수 있다. 이 작업을 두 사람이 번갈아 가면서 할 때 자기 차례에서 더 이상 허용된 작업을 못하는 사람이 지고(lost) 상대방은 이기게(win) 된다. 단 이 게임에는 몇 가지 제한 사항이 있다.
1) 만일 앞 차례에서 개의 돌을 꺼냈다면 다음 차례 사람은 다시 같은 수의 돌 을 연이어 꺼낼 수 없다. (반복 금지, 따라하기 금지의 원칙)
2) 제일 처음 시작하는 사람은 $s_1$, $s_2$, $s_3$ 중에서 어떤 것이라도 선택할 수 있다.
3) 자신의 차례가 왔을 때 “PASS”를 선언할 수 있다. “PASS”는 어떤 작업도 하지 않고 자신의 차례를 상대방에게 넘기는 동작이다. 즉 항아리 속 돌의 개수는 변함이 없다.
4) PASS역시 반복금지 원칙에 제한을 받는다. 즉 PASS를 받은 사람이 다시 연이어 PASS를 선언할 수는 없다. 즉 PASS를 받은 사람은 몇 개의 돌을 들어내어야 한다.
5) 단 이 PASS는 게임 중 최대 1번만 사용할 수 있다. 즉 한번 PASS를 사용한 사람은 이후에 다시 PASS 선언을 할 수 없다.
6) 자신의 차례가 왔을 때 위에서 허용한 동작(operation)이나 PASS 선언을 할 수 없으면 그 차례의 사람이 게임에서 패하게 되고 상대방이 이기게 된다.
[입출력]
입력 파일 jug.inp 의 첫 줄에는 자신의 차례에서 선택할 수 있는 돌의 갯수를 나타내는 3개의 정수 $s_1$, $s_2$, $s_3$ 이 주어진다. 그 조건은 다음과 같다. $1 \le s_1 < s_2 < s_3 \le 10$. 이어지는 10개의 줄에는 초기상태 항아리에 담긴 돌의 갯수 $N_i (3 \le N_i \le 100)$가 주어진다. 여러분은 이 10개의 에 대하여 그 승자를 {F,S}에서 골라 문자로 출력해야 한다. 단 두 사람 F와 S는 항상 최선을 다한다고 가정한다. 즉 이길 가능성이 1%라도 있으면 그 수를 선택해야 한다.
[예제]
$s_1 = 2$, $s_2 = 3$, $s_3 = 6$ 개 인 경우를 생각해보자. 만일 $N =0$이면 F가 처음에 PASS를 하면 더 이상 S가 PASS를 연이어 하지 못하므로 F가 Win이다. $N=1$인 경우 F는 자신의 차례에서 돌을 꺼낼 수 없기 때문에 할 수 없이 “PASS“를 선언해야 한다. 그러면 이 PASS를 받은 두번째 사람 S는 반복 금지 원칙에 의해서 연속하여 ”PASS“를 선언할 수 없고 또한 돌을 2, 3, 6개 들어낼 수도 없기 때문에 더 이상 작업을 할 수 없게 된다. 따라서 $N=1$이면 F가 winner가 된다. 정리하면 Win(0)=Win(1)=F가 된다.
$N=2$일 때를 생각해보자. 만일 F가 PASS를 선언하면 S가 2개를 모두 들어낸다. 이 상황에서 F는 또 다시 PASS를 선언할 수 없기 때문에 $N=2$인 경우 F는 지고 승자는 S가 된다. 만일 F가 2개 모두를 들어내면 $N=0$이 된다. 이 경우 S는 PASS를 선언하면 F는 다시 PASS를 선언할 수 없으므로 이 경우에도 S가 승자가 된다. 따라서 $N=2$인 경우에 승자는 S가 된다. 따라서 Win(2)=S가 된다.
$N=3$인 경우에는 좀 더 복잡하다. 시작 상태에서 F가 할 수 있는 수(move)는 [PASS, 2, 3]이 가능하다. 그 결과 항아리에 남아있는 돌의 갯수는 각각 {3, 1, 0}이 된다. 아래 게임트리(game tree)를 참고하여 게임이 어떻게 진행되는지 살펴보자.
그리고 다음에 제시된 두 입출력 예제를 이용해서 승패가 어떻게 결정되는지 확인해보자.
|
jug.inp |
jug.out |
jug.inp |
jug.out |
|
2 3 6 // 1 2 3 4 5 6 7 13 24 35 |
F S S F F F S F F F
|
1 2 5 // 1 2 3 4 5 6 7 13 24 35 |
S F F S F F S S F F
|
[풀이] O($N * 2 * 5 * 2$)
세상 반가운 게임dp다.
왜 반갑냐면 처음 알고리즘 동아리 알콜을 들어가서 처음 배운 dp에 이게 나왔다.
내 기억에 아마 종만북에 실렸던 걸로 기억하는데, 그때 꽤 오랫동안 고민했고, 조금 충격적인? 문제였어서 아직 기억하나보다.
본론으로 들어가서, dp table을 이렇게 정의하겠다.
$dp[i][j][k][t] =$ $i$개 돌이 남았고, $j$번 패스를 사용했으며, 이전의 선택은 $k$이고, 현재 $t$의 턴일때 승리하는 사람
그리고, 게임dp의 핵심인 '모두가 최선을 다 한다' 의 조건에 의해 아래의 조건이 생기는 셈이다.
"모두가 최선을 다 한다 => $t$의 turn 일때, $t$가 승리하는 경우가 하나라도 있으면 $t$가 승리하고, 하나도 없을 경우 $!t$가 승리한다"
이 문장이 핵심이다.
즉, 위 dp table정의에 따라 점화식을 세울 때, 현재 turn의 상태에 따라 dp 점화식이 달라진다.
다시 강조하자면,
$F$의 차례에 $F$가 이기는 경우가 하나라도 있으면 그 턴을 기준으로는 $F$가 무조건 승리한다.
반대로, $F$가 이기는 경우가 하나도 없는 경우에만 $T$가 승리한다.
$T$의 차례에는 정반대가 된다.
위에서 언급한 내용들과, 문제에 조건에 따라 점화식을 정리해보면
case 1) if turn = $F$(이하 0)
dp[idx1][idx2][idx3][idx4] = min(1, dp[idx1 - s[i]][idx2][i][!idx4]),
if (idx2 == 0 && idx3 != 3)
dp[idx1][idx2][idx3][idx4] = min(dp[idx1][idx2][idx3][idx4], dp[idx1][1]][3][!idx4])
case 2) if turn = $T$(이하 1)
dp[idx1][idx2][idx3][idx4] = max(0, dp[idx1 - s[i]][idx2][i][!idx4]),
if (idx2 == 0 && idx3 != 3)
dp[idx1][idx2][idx3][idx4] = max(dp[idx1][idx2][idx3][idx4], dp[idx1][1]][3][!idx4])
case별로 차이점은 min이냐 max냐. 즉, turn이 0이면 0인게 하나라도 있는지 찾고, turn이 1이면 1인게 하나라도 있는지 찾는다.
내가 이런 문제를 정확하게 기억하는게, dp table에서 turn을 없애고도 풀 수 있는 방법이 있다고 얘기하며 설명해주던게 뇌리에 박혀있어서 기억한다.
문제는 그 방법이 뭔지 까먹었다는 건데...
기억 나는대로 다시 코드를 짜서 테스트해봐야겠다.
