잘 푸신 것 같습니다. 생각의 흐름을 간단히 적어 봅니다.
먼저 주어진 돌의 총 개수가 홀수라면 돌을 한 개만 가져가면 반드시 승리합니다(상대도 돌을 하나씩밖에 가져갈 수 없게 되므로). 반대로 주어진 돌의 총 개수가 짝수라면, 두 플레이어는 절대로 돌을 홀수 개 가져가지 않습니다.
양쪽이 모두 짝수 개의 돌을 가져가다 보면 결국은 원래 짝수 크기였던 돌무더기들은 완전히 없어지고, 홀수 크기였던 돌무더기들은 크기가 1이 되어 남을 것입니다. 그리고 이렇게 남은 돌무더기는 짝수 개일 것이므로 승패에 영향을 주지 않습니다.
따라서 문제를 K와 각 돌무더기의 크기를 모두 2로 나눈(.5는 버림) 더 작은 문제로 줄일 수 있게 되고, 줄어든 문제에서 다시 "총합이 홀수면 돌을 하나만 가져가고, 아니면 문제를 절반으로 줄이는" 과정을 반복하면 됩니다.
생각해 볼 부분은 "이 논리에 따를 때 내가 이길 수 없는 상황이라면, 정말로 내가 어떤 선택을 해도 상대방에게 승리수가 있는가?"일 것 같습니다. 이건 직접 생각해 보시면 좋겠습니다.

ksjb2897 1년 전
오랫동안 고민한다음 겨우 풀었습니다 ㅠ
우선, 문제가 영어라 읽기 귀찮으신 분들을 위해 문제를 소개하자면, 님 게임인데, 처음에 최대로 가져갈 수 있는 돌의 개수 K개가 정해져 있고, 그 다음부터는 상대방이 가져간 돌 개수보다 적게 가져갈 수 있으며, 마지막에 돌을 가져가서 모두 없앤 사람이 승리하는 게임입니다.
근데, 알고리즘은 생각해 냈지만, 여러 개의 케이스를 손으로 계산해보면서 경험적으로 얻고 약간의 수학적 감각을 더해서 푼거라 엄밀하게 왜 이 풀이가 맞는지 모르겠습니다. 다른 사람들 코드를 봤는데 이해도 잘 안되고 다른 풀이인가 싶기도 하고요.. (이게 왜 플래3..? 전 정말 어려웠슴다 ㅠ 처음에 상황 여러개로 쪼갠다음 그런디 수 찾아보기도 하고 근데 시간복잡도 넘쳐나서 다른 방법으로 우회함..)
우선, 제 알고리즘을 소개하겠습니다.
매 테스트 케이스 마다, 반의 수를 N, 최대 가져갈 수 있는 수를 K, 각각의 학생수를 a1, a2, ..., aN이라고 합시다.
이 때, 여러번의 검증을 해서, 하나라도 승리가 나오면 선공이 승리할 수 있다.
검증은 1부터 K까지 중의 수 중, 2의 거듭제곱 꼴에 대해서 진행하면 되고, 그 수를 x라고 해보자. (즉, x는 2의 거듭제곱 꼴)
1) a1, a2, ..., aN을 모두 x의 배수로 내림한다.
2) 내림한 수, a1 부터 aN까지 모두 더하고 그 수를 sum이라고 하자.
3) sum이 2*x의 배수면 패배, 아니면 승리이다.
이해를 돕기 위한 예를 들면,
N = 3, K = 7이라고 하고, a1 = 3, a2 = 8, a3 = 23이라고 해봅시다.
검증1 : x = 1
a1 = 3, a2 = 8, a3 = 23이 됨.
더하면 sum = 34이고, 34는 2(x*2=2)의 배수이므로 패배.
검증2 : x = 2
a1 = 2, a2 = 8, a3 = 22이 됨.
더하면 sum = 32이고, 32은 4(x*2=4)의 배수이므로 패배.
검증3 : x = 4
a1 = 0, a2 = 8, a3 = 20이 됨.
더하면 sum = 28이고, 28은 8(x*2=8)의 배수가 아니므로 승리.
검증1, 검증2, 검증3중에 하나라도 승리가 있으므로(검증3이 승리) 선공이 승리.
이런식입니다. 그래서 제 질문은,
1. 이 알고리즘이 왜 정당한가?
2. 다른 사람들도 이러한 비슷한 논리구조의 알고리즘으로 풀었는가? 만약 아니라면 어떻게 풀었는가?
입니다 ㅠㅠ 고수님들 도와주십숑 ㅠㅠ