Hackerrank weekly challenges 9에 참가했었는데, 재밌는 일이 일어났습니다. challenge기간 중 문제를 푼 모든 사람이 틀렸고.. 심지어 문제 낸 사람이 생각한 답안도 틀렸던 거죠-_-
때문에 이 문제는 무효로 처리됐고 지금은 general case에 대한 답안을 찾고 있는 상황이네요..
참가당시 이 문제에 막혀서 머리에 쥐가나도록 생각을 쥐어짜도 제한조건 내에 답을 찾는 알고리즘을 생각해내지 못했었는데.. 문제가 정말 너무 어려웠던 거네요ㄷㄷ
문제를 간단히 설명하자면, N개의 체스말 Knights의 위치가 주어지고, 이들의 이동 규칙은 (-2,-1)혹은 (-1,-2)로만 이루어집니다. 두명의 플레이어는 돌아가면서 1~K개의 말을 선택하여 1~X번만큼 움직일 수 있어요. 더 이상 말들을 움직일 수 없을 때 게임에 패배하는 거구요. 이 때 최적전략에서의 승자를 예측하는 겁니다.
N은 최대 2만이고, K는 N 이하이며, X는 1~5사이의 값입니다. 좌표값 x,y는 [0,300) 범위 안에 있구요.
전 이문제에 대해서 상태공간을 어떻게 잡을지조차 감을 못잡았는데ㅠㅠSprague Grundy theorem을 써서 해결하는 게 의도한 해법이었다고 하네요. 그런데 예외가 발생했구요.
restart
Hackerrank - A game of knights
Hackerrank weekly challenges 9에 참가했었는데, 재밌는 일이 일어났습니다. challenge기간 중 문제를 푼 모든 사람이 틀렸고.. 심지어 문제 낸 사람이 생각한 답안도 틀렸던 거죠-_-
때문에 이 문제는 무효로 처리됐고 지금은 general case에 대한 답안을 찾고 있는 상황이네요..
참가당시 이 문제에 막혀서 머리에 쥐가나도록 생각을 쥐어짜도 제한조건 내에 답을 찾는 알고리즘을 생각해내지 못했었는데.. 문제가 정말 너무 어려웠던 거네요ㄷㄷ
문제를 간단히 설명하자면, N개의 체스말 Knights의 위치가 주어지고, 이들의 이동 규칙은 (-2,-1)혹은 (-1,-2)로만 이루어집니다. 두명의 플레이어는 돌아가면서 1~K개의 말을 선택하여 1~X번만큼 움직일 수 있어요. 더 이상 말들을 움직일 수 없을 때 게임에 패배하는 거구요. 이 때 최적전략에서의 승자를 예측하는 겁니다.
N은 최대 2만이고, K는 N 이하이며, X는 1~5사이의 값입니다. 좌표값 x,y는 [0,300) 범위 안에 있구요.
전 이문제에 대해서 상태공간을 어떻게 잡을지조차 감을 못잡았는데ㅠㅠSprague Grundy theorem을 써서 해결하는 게 의도한 해법이었다고 하네요. 그런데 예외가 발생했구요.
general한 해법은 없는 걸까요?
10년 전