BOJ 10837 동전 게임

쉬워보였지만... 적어도 나한테는 여려운 문제였다. 엄청 오래 고민했다.
인터넷에서 찾은 KOI solution에는 코드밖에 나와있지 않아서... 이해를 못했다.
결국 내가 생각해서 AC를 받긴했다.

깔끔한 풀이는 아니지만... 좀 먼 길 돌아가는 풀이 같긴하지만 기록해 보려고 한다.

내가 헷갈렸던 것인데, 일단 문제에서 요구하는 것은 이길 수 없는 점수인지가 아니라 나올 수 있는 점수인지 아닌지 판별하는 것이다.

승패가 결정이 나면 더이상의 게임 진행을 하지 않으므로 주어진 점수 a : b가 불가능한 점수이려면 a : b 바로 이전의 점수에서 승패가 결정나야 한다. 그렇지 않으면 가능한 점수일 것이다.

그런데 a : b 바로 이전의 점수는 어떻게 정할까?
a > b일 경우 a-1 : b를 이전 점수로, a < b인 경우 a : b-1을 이전 점수로 설정한다.
즉, 최대한 차이가 덜 나는 점수, a : b가 성립할 수 있는 가능성이 가장 큰 점수로 직전 점수를 선정하는 것이다.

그리고 게임 순서는 a>b, a-1 : b인 경우는 b가 할 차례이고, a<b, a : b-1인 경우는 a가 할 차례이다. 이것도 역시 a : b가 성립할 가능성이 가장 크도록 설정한다.

a > b인 경우는 a가 이긴 상태로 끝난 것이므로 a-1 : b에서 b가 남은 라운드에서 모두 점수를 얻고, a는 남은 라운드에서 점수를 전혀 얻지 못해도 a가 이길 수 있는지 봐야한다. 그렇게 해도 a가 이기게 되다면 a-1 : b에서 끝내야 하므로 a : b까지 갈 수 없다. 그리고 만약 비기는 결과가 나온다해도 a : b까지 갈 수 없다. 비기려면 b는 모든 라운드에서 점수를 따야 하는데, a : b를 만들기 전에 b가 한 라운드에서 점수를 못 얻으면 a-1 : b에서 a의 차례가 되고 이 경우는 b가 이길 수 없게 되는 것이므로 a-1 : b에서 끝나게 된다.

a > b인 경우랑, a < b인 경우랑 조금 다른 점은 누구 차례인지랑 그에 따라 남은 라운드 수가 좀 다른 것이다. 주의해서 코딩해야하고, a=b인 경우는 (입력 값으로 a, b모두 k이하의 값이 주어지므로) 항상 가능한 경우일 것이다.

KOI solution에 나오는 풀이를 이해하고 싶은데 아직은 이해 못 하겠다.
나중에 기회가 되면 다시 생각해 봐야겠다.