알고스팟 고수분들.. 이 문제 한번 풀어보시겠어요?

  • restart
    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한 해법은 없는 걸까요?


    6년 전
1개의 댓글이 있습니다.
  • VOCList
    VOCList

    말이 여러마리인게 에러겠네요 ㅜㅜ


    6년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.