백준 9655. 돌 게임

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

9655번: 돌 게임

 

DP 문제를 안 푼지 좀 된것 같아서 (사실 풀기 싫어서 안풀었다...) 이제부터는 dp 문제들을 좀 다시 풀어보려고 한다.

좀 쉬운 문제들 부터 ...

 

게임은 N개의 돌이 있을때 1개 또는 3개의 돌을 가져갈수 있고, 마지막 돌을 가져가는 사람이 이기는 게임이다.

즉 마지막에 돌이 3개 또는 1개 남았을때 순서가 오는 사람이 이기는 게임이다. 

 

한 사람에 대하여 우선 3개의 돌을 가져갈수 있는지 확인한다.

가져갈수 있다는 것은 내가 3개의 돌을 가져가도 상대가 게임을 이기지 않는지 확인하는 것이다. 

현재 돌에서 3개를 뺐을때 남은 돌이 4개 이상이면 괜찮으므로 3개를 가져가고 턴을 넘긴다. 

그렇지 않다면 3개는 가져갈수 없으므로 나머지 선택지인 1개를 가져갈수 밖에 없다. 

 

이렇게 순서를 주고 받다가 남은 돌의 수가 3개 이하가되면 게임이 끝나고, 게임이 끝날때 순서인 사람이 이기게 된다.

 

주의할 점: 

- 최초에 주어지는 돌이 2개라면 무조건 두번째 차례인 창영이가 이기게 된다.

 

 

 

---

dp 문제를 풀려고 푼 문젠데 처음에 풀었을때 사실 dp가 아닌 방법으로 풀어서 다시 풀어봤다.

 

dp[N] = M 은 돌이 N개 일때 최소 M번의 턴 진행함. 

 

점화식은 

dp[i] = (min(dp[i-1]+1, dp[i-3]+1) 

 

우선 N=1 일때는 M=1 일 것이다.

N=2 일떄는 상근이가 1개를 가져가고 창명이가 1개를 가져가므로 M=2. 

N=3 일때는 상근이가 처음에 3개를 가져가면 끝나기 때문에 M=1.

 

N=4 부터는 케이스가 나뉜다. 

돌은 1개 또는 3개만 가져갈수 있으므로 

이전에 누군가 1개의 돌을 가져갔다면 이전 돌의 갯수는 3개일 것이다. 

아니면 누군가 3개의 돌을 가져갔다면 이전 돌의 갯수는 1개일 것이다.

 

따라서 N=4 일때 진행한 최소 턴 수는

N=3일때 진행한 최소 턴 수에서 한 번더 한 횟수, 

N=1일때 진행한 최소 턴 수에서 한 번더 한 횟수 중 작은값이다.

작은 값인 이유는 둘 모두 완벽하게 게임을 진행한다고 했기 때문이다. 

 

마지막으로 

턴 1번 진행시 상근이가 먼저 시작하기 때문에 상근이의 승리.

턴 2번 진행시 상근-창영, 창영에서 끝나기 때문에 창영이 승리.

턴 3번 진행시 상근-창영-상근, 상근에서 끝나기 때문에 상근이 승리.

 

따라서 d[N] 값이 홀수면 상근이, 짝수면 창영이의 승리다.