[editorial] Run Programming Contest F - 가위바위보

  • Being
    Being

    먼저 간단히 생각할 수 있는 부분은, 현재 살아있는 사람이 누구누구이냐에 따라 게임 양상이 달라질 것이라는 점입니다. 즉, 현재 살아있는 사람을 표현하기 위해서 2^N 가지의 state가 존재하게 됩니다. 각 스테이트의 결론을 얻었다면, memoization을 사용하여 중복된 연산을 피할 수 있겠죠.
    단순하게 접근한다면, 각 state에서 각 사람이 낼 수 있는 3^N가지의 조합을 모두 따라간 후에, 자신의 선택과 조합하여 나온 결과를 가지고

    • 이기거나,
    • 비기거나,
    • 지게 됩니다. 비기는 경우는 우리에게 관심이 없고, 이기거나 지는 경우에만 관심이 있습니다. 이기는 경우는 더 이상 게임이 어떻게 진행되던 나몰라라 하면 됩니다. 남은 사람들 중 누군가가 지겠죠 뭐. 관심없습니다. 지는 경우가 중요한데, 지는 경우는 '누구와' 함께 지느냐가 중요한 요인으로 작용합니다. 만약에 우리가 3^N가지 경우를 모두 탐색했다면 누가 졌는지를 판단하기 비교적 쉽습니다. 그런데, 이 경우 다소간 느립니다. 대충 2^N * 3^N? 의 complexity를 갖게 되겠죠? 나올 지 안 나올 지 자신은 없지만 좀 힘들어 보이네요. 여기서 조금 더 논리를 전개해 보면, 한 판의 가위바위보가 발생했을 때 가위가 하나 발생했든 두 개 발생했든 세 개 발생했든 그건 게임의 흐름을 판가름하는 데에는 중요하지 않습니다. 가위가 있었느냐 없었느냐가 중요한 요인이 되는 것이죠. 그래서 DP 테이블을 하나 정의합니다. d[p][r][p][s] := p번째 사람까지 고려하였고, 바위가 등장하였고/등장하지 않았고, 보가 ... 인 상황이 발생할 확률 (r, p, s elem {0, 1}) 이 DP 테이블을 state마다 계산하려면 8N 번의 연산이 필요합니다. 이 DP 테이블을 계산했다고 치고, 다시 한 번 게임의 결과를 생각해 봅시다.
    • 이기거나
    • 비기거나
    • 지는 경우가 있습니다. 여기서 비기는 경우는,
    • 모두가 같은 것을 내거나 ( (r ^ p ^ s) && (r + p + s) == 1)
    • 가위/바위/보가 모두 적어도 하나 존재하거나 (r && p && s) 의 두 가지 경우가 있습니다. 즉, 이기거나 지는 경우에만 관심이 있기 때문에 가위/바위/보가 모두 존재하는 경우나 하나만 존재하는 경우는 고려할 필요가 없습니다. 그러면 3가지 각 시나리오에 대해 (e.g. 가위와 바위만이 나타났다) 자신의 선택에 따라 이기고 지는 경우가 다를텐데, 이기는 경우야 더 이상 관심이 없지만 지는 경우에는 위에서 언급했듯 '누가' 졌는지가 중요하기 때문에 문제가 됩니다. 따라서 이 '누가' 졌는지를 결정하기 위해 2^N번의 탐색을 합니다. 결과적으로 우리가 한 일은 3^N번의 탐색을 가위/바위/보 모두 등장하는 경우를 고려하지 않음으로써 2^N번의 탐색으로 감소시킨 것이지요. 여기까지 제가 문제를 푸는 과정을 쫓아왔는데, 보면 이 과정에 개선의 여지가 있습니다. 내부적인 DP 테이블 같은 것은 사실은 큰 의미가 없습니다. 더 간단하게 문제를 풀기 위해서는, 각 state마다 3^N가지의 결과를 모두 따져보는 과정에서 '비기는' 경우가 발생하는 경우를 미리 프루닝(가지치기)하면 됩니다. 이렇게 하면 실제로는 3*2^N회의 탐색을 수행하게 되겠지요. 그렇다면 DP 테이블 구하고 뭐고 간에 난리를 칠 필요가 굳이 없는 것이지요.
      [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    15년 전
9개의 댓글이 있습니다.
  • JongMan
    JongMan

    2^N * 3^N 이라고 해 봐야, 3 의 승수가 항상 N 이 아니라 남아 있는 사람의 수에 따라 줄어들기 때문에 속도에 큰 문제가 있지는 않을.. 겁니다. 3^10 = 59049 을 계산하는 경우는 전부 남아 있는 경우 한 경우밖에 없고, 3^9 = 19683 을 계산하는 경우는 열 개밖에 없고... 이렇게 다 더해보면 전체 연산의 수가 2^20 이 됩니다. 로컬에서는 최악의 테스트 케이스들도 금방 나오길래 용감히 섭밋했는데 쳇 ㅋㅋㅋㅋ
    근데 r=s=p=0 때문에 삽질하다가 최적화고 뭐고 못해버렸네용. :-( 아웅 쥐쥐


    15년 전 link
  • Being
    Being

    에이 2^2N은 더 줄어들잖아요...:$


    15년 전 link
  • Being
    Being

    그나저나, r = s = p = 0인 경우가 제가 어떻게 답(???)이 나온건지 도통 신기하네요 -_-b
    테스트 데이터 중에는 무한히 비기는 경우도 존재해서, 그 경우 0을 출력해야 합니다.


    15년 전 link
  • JongMan
    JongMan

    4초라는 시간 제한에 걸릴 거라곤 생각도 안 했단 얘기지. -_-; 2^2N 보다 빠르다곤 말 안했스.. ㅜㅜ


    15년 전 link
  • Being
    Being

    그래서 아직도 궁금한 것이.. 채점 머신 사양도 무척 좋았는데 무한루프 도신 건 아닌가 싶기도 하네여 흠 ㅠㅠ


    15년 전 link
  • JongMan
    JongMan

    최적화 플래그가 없어서 TLE 인듯;; r=s=p=0 과 기타등등 다 해도 무한루프는 안돌아여 ㅠㅠ


    15년 전 link
  • VOCList
    VOCList

    본능적으로 정답을 찍는 류본좌의 소스 ㅜㅜ


    15년 전 link
  • nocut98
    nocut98

    아... 타고난 분.... ㅋㅋㅋㅋㅋㅋㅋ


    15년 전 link
  • Yongrok
    Yongrok

    -ㅅ- 출제하고 솔루션을 작성한 저도 어떻게 나왔는지 신기할 따름입니다 ㅠㅠ아 나름 출제하면서 재미있는 문제라고 생각했는데 io 수정 크리 ㅠㅠ 얼룩진 문제가 되었군요 ㅠ
    죄송할 따름입니다 ㅠㅠ


    15년 전 link

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