최근 BOJ에 정체불명의 게임 문제들이 많이 추가되었다. 님 게임 문제뿐 아니라, 그리디하게 풀 수 있거나 자료구조를 이용하는 문제도 있고, 여러 모로 며칠간 재밌게 푼 것 같아 풀이를 정리해보려 한다. (이걸 쓰려고 티스토리 블로그도 개장했다. 이 글 다음 글은 몇 년 뒤에 올라올지 나도 잘 모르겠다.)
우선 이 문제들의 대부분을 풀기 위해서는 기초 지식으로 Sprague-Grundy Theorem, 혹은 '그런디 넘버'를 알아야 한다. 하지만 이 이론의 엄밀한 증명을 읽어 보기가 귀찮은 대다수의 분들을 위해, 간단히 필요한 부분만 추리면 아래와 같다. 수학적 배경은 나도 모르기 때문에 외워야 하는 부분만 뽑아 봤다. 만약 더 자세한 내용이 필요하신 분은 [위키 링크]를 참조하시길 바란다.
보통은 다음의 조건들을 만족하는 게임의 승자를 결정하는 문제가 그런디 넘버로 풀린다. (엄밀하지는 않은데 웬만하면 아래 조건을 만족하면 다 된다.)
게임판의 상태가 주어졌을 때, 누구의 턴이든 관계없이 할 수 있는 행동의 집합이 동일해야 한다.
예를 들어, 바둑의 경우엔 동일한 바둑판에서도 선공은 흑돌만, 후공은 백돌만 움직일 수 있기에 행동의 집합이 동일하지 않다.
게임판의 상태에 사이클이 없어야 한다.
50수 규칙이 없는 체스 게임이 있다고 하자. 이 게임에서는 흑과 백이 한 커맨드씩 두고, 그 다음턴엔 바로 전에 했던 행동을 undo하는 방식으로 무한히 같은 게임판을 반복시킬 수 있다.(둘 다 킹만 남은 상황을 생각해보자). 이처럼 사이클이 생길 수 있는 게임에서는 그런디 넘버의 사용이 힘들다.
선공과 후공의 목표가 동일하다.
이렇지 않은 게임이 문제로 나온다면 대부분 선공은 무언가를 최적화하려 하고, 후공은 그것을 방해하는 포지션을 맡는다. 이렇지 않고, 선공과 후공이 동일한 목표를 두고 경기하는 게임에서만 그런디 넘버를 사용해 보자.
보통은 '더 이상 행동을 할 수 없는 플레이어가 패배한다' 가 조건이지만, 조금 변형하면 더 이상 행동할 수 없을 때 이길 수도 있다. 후자의 경우는 전자보다 조금 더 어렵다.
이 조건들을 모두 만족하는 가장 간단한 게임으로는 '님 게임' 이 있다. 님 게임이 무엇인지는 [여기]에서 대충 확인하자. 하지만 아직 이걸 풀 수는 없으니 내용만 읽고 끄도록 하자.
만약 위와 같은 게임이 있다면, 게임을 시작하는 순간 승패는 결정이 난다. 선공이 반드시 이기거나, 그럴 수 없다면 후공이 반드시 이긴다. 우리 목표는 이러한 게임들에서 선공과 후공 중 누가 이기는 지 알아내는 것이다.
Grundy number란, 게임판의 각 상태별로 붙여 놓은 수를 말한다. 의미는 잘 모르겠으므로, 그냥 빨리 문제를 풀기 위해 grundy number가 어떻게 매겨지는지만 확인해 보자.
먼저, 아무 것도 할 수 없는 게임판, 즉 게임이 끝난 게임판의 grundy number는 0이다. (by definition)
그 이후는 귀납적으로 정의되는데, 만약 어떤 게임판에서 단 한 번의 행동으로 grundy number가 0, 1, ... , k인 게임판을 모두 방문할 수 있다면, 그러한 k 중 가장 큰 k에 대해 이 게임판의 grundy number는 k+1이다. 즉, 한 번의 행동으로 grundy number가 0인 게임판을 방문할 수 없다면, 바로 패배하는 게임판이 아니더라도 grundy number가 0인 것이다.
예를 들어 위에 링크로 소개한 nim game에서는, 돌이 0개인 경우엔 아무 것도 할 수 없으므로 그런디 넘버가 0,
돌이 1개인 경우엔 0개인 상태로 보낼 수 있고, 0개인 게임판의 grundy number는 0이므로 이 게임판의 grundy number는 1,
돌이 2개인 경우엔 돌이 0개, 1개인 상태로 보낼 수 있고, 각각의 grundy number가 0, 1이므로 돌이 2개인 게임판의 grundy number는 2가 된다.
님 게임이 이러한 게임 중 가장 간단한 이유는, 보다시피 그냥 돌의 개수가 grundy number가 되기 때문이다.
어떤 게임에 대해, 게임판 하나에서 선공이 이기는 조건은 grundy number > 0이면 된다. 엥? 그럼 돌이 0개만 아니면 선공이 이기나?
실제로 그렇다. 그냥 시작하자마자 다 가져가면 끝이니까..
하지만 님 게임은 이러한 게임판이 여러개 있는 경우가 대부분인데, 그런 경우엔 어떻게 승패를 결정할까? 예를 들면, 아까부터 예시로 들고 있는 님 게임에서는 돌무더기가 여러 개 있고, 각 돌무더기마다의 grundy number는 알고 있지만, 최종적으로 이 무더기를 모두 사용하는 게임에서 마지막 돌을 가져가는 승자가 누구인지는 바로 알기가 쉽지가 않다.
답은 그냥 모든 게임판의 grundy number를 bitwise xor 연산하여, 그것이 0이 아니면 선공 승, 아니면 후공 승이다. 그냥 선공이 0으로 만들어 넘겨주면, 상대가 무엇을 하든 그런디 넘버의 총 xor이 다시 0이 되게 받아치는 방법이 존재하고(이 부분은 증명이 필요하나 적지 않는다), 언젠가 게임이 끝났을 때, 그 게임은 xor 값이 0인 상태임이 자명한데, 그 게임을 받은 사람이 상대방이기 때문이다. 즉, 내가 질 일이 없으므로 내가 이긴다. 좀 더 엄밀한 내용이 필요하면 더 자세히 쓰여 있는 블로그를 찾아보도록 하자.
이제 위의 님 게임을 풀 수 있게 되었다! 그냥 주어지는 N개의 정수를 모두 xor 연산하여 0이 아니면 koosaga, 0이면 cubelover를 출력하면 정답이다. 혹시 제출해보고 싶다면 [여기]로.
이제 이걸 외우고 나면(증명이 하나도 없으니 '이해한다' 라는 표현 대신 '외운다' 라는 표현을 사용했다), 새로 올라온 게임 문제들 중 반 정도가 넘는 수를 간단하게 풀어버릴 수 있다. 게임판을 정의하고, 모든 게임판에서 행동 한 번을 하여 grundy number를 모아서(재귀적으로 DP를 하면 된다) 처음 게임판들의 grundy number를 결정하고, 각 게임판의 grundy number를 xor해서 0보다 크면 koosaga, 0이면 cubelover가 이긴다고 생각하면 된다.
아래는 각 문제에 대한 풀이이다. 문제 이름을 누르면 문제 링크로 가고, 풀이를 누르면 풀이가 열린다.
<<<주의!>>> 아래의 문제들은 대부분 풀이를 보면 재미가 확 떨어집니다. 위의 개념만 숙지했다면, 얼마든지 혼자 힘으로 풀 수 있는 문제가 대부분일 것입니다. 시도해보시고 정 안될 때만 참고자료로 열람해주세요!
전형적인 님 게임이다. 피보나치 수는 범위 내에서 몇 개 있지도 않으므로, 돌의 개수 X가 주어졌을 때, 피보나치 수를 하나씩 빼 보면서 grundy number를 모으면 돌이 X개 있을 때의 grundy number를 계산할 수 있다. 주어지는 N개의 돌더미의 grundy number를 모두 xor해서 0인지 아닌지를 체크하면 된다.
마찬가지로 각 궁전에 대해 독립적으로 체크하면 되는데, 그냥 DP로 체크하면 필요한 연산량이 3000^3에 달하게 되어 시간 내에 넣기가 힘들다. 이처럼, grundy number를 구해야 하는 게임판의 상태가 너무 많거나, 계산량이 너무 많은 문제의 경우 일반적으로 통용되는 야매 풀이가 있다. 물론 정정당당하게 무언가를 유도해서 풀어내면 좋겠으나, 우리에게 주어진 대회 시간은 너무 짧기에.. (사실 이번 글에서 다루고 싶은 가장 큰 주제가 이 야매 풀이이다.)
우선 작은 범위 내에서 grundy number를 모두 출력해본다. 출력은 마음대로 해도 되는데, 어떻게 해보냐에 따라 규칙이 쉽게 보일 수도, 전혀 안 보일 수도 있기 때문에 다각도로 시도를 해 봐야 한다.
일단은 보이는 게 없으니 (r,c,g(r,c))를 모두 출력해보도록 하자.
뭔가 r=0일때 말고는 규칙이 없는 것 같다. 근데 잘 관찰하면, 혹은 잘 생각해보면 궁전이 (r,c)에 있을 때와, (c,r)에 있을 때의 grundy number는 같음을 알 수 있다. 할 수 있는 행동의 집합이 대칭으로 완벽히 동일하기 때문에 자명한 사실일 것이다. 어 그렇다면..? 왠지 행렬로 출력해보면 대각선 기준으로 뭔가 예쁜 게 나올 것 같다. 한번 해보도록 하자. 적당히 30*30 정도를 돌려 보면 아래처럼 나온다.
앗 뭔가 보인다. 3행 단위로, 또는 3열 단위로 좀 cyclic하게 돌아가고 있는 것 같다. 맨 왼쪽 위의 3*3 사각형을 관찰하면 쉽다.
그럼 어차피 r mod 3 != 0이라면 r mod 3 == 0인 상태에서 적당히 사이클릭하게 회전을 시켜주기만 하면 되므로, r과 c가 모두 3의 배수일 때만 다시 출력해보자. 범위를 넓혀 3의 배수인 행과 열에 대해서만 출력해 보면 아래와 같다.
0행은 순차적으로 오르고 있고, 다른 행들은 0행의 permutation 형태임을 볼 수가 있다.
잘 관찰하면, R행의 grundy number들은 0행을 우선 갖다놓고, R을 이진수로 나타냈을 때, 2^i에 해당하는 비트가 켜져 있다면 매 2^i번째 부분을 스왑하는 작업을 모든 비트에 대해 시행한 결과임을 알 수 있다. (진짜?)
예를 들어 1행은 0행의 상태에서 매 짝수 번째 원소와 홀수 번째 원소를 스왑한 형태이고, 2행은 0행의 상태에서 네 칸마다 앞 두 칸과 뒤 두 칸을 스왑한 형태이며, 3행은 먼저 1행의 연산을 적용하고, 또 2행의 연산을 이어 적용한 형태이다.
아마 13행은 8 + 4 + 1행이므로, 8칸 단위로 스왑, 4칸 단위로 스왑, 1칸 단위로 스왑을 0행에 대해 각각 적용하면 될 거다.
이제 규칙을 알아냈으니 코딩만 잘 하면 된다.
사실 이 뒤로 거의 모든 문제의 풀이를 적었었는데, 갑자기 블루스크린이 뜨더니 모든 글이 날아갔다.
왜인지 임시저장 기능도 먹통이어서 전부 날려먹었는데, 다행히 크롬 탭 중 미리보기를 켜 뒀던 탭이 복구되어 거기서 복사해서 긁은 결과 위까지는 살렸다. 복사하는 과정에서 태그가 좀 깨진 것도 있을 텐데, 고치기 너무 귀찮고 지금 멘탈이 남아 있는 상태가 아니어서 그냥 진행하기로 한다.
뒤 문제 풀이를 꽤 자세하게 적었었는데, 더 이상 자세히 쓸 여력이 없어 대강 쓰려고 한다. 궁금한 점이 있다면 댓글을..
정말 너무 충격적이다. 요즘 블로그에 자동저장 기능이 없을 줄은 몰랐다. (있어도 제대로 안 되면 없는 거나 마찬가지다)
크롬의 플래시 차단 규칙이 바뀌고 어쩌고 하던데, 지금은 임시저장 버튼을 눌러도 임시저장이 안 된다. 하하. 너무 좋은 기능
하튼 시작한 김에 끝을 보기 위해 다시 달리기로 한다. 지속적으로 게시를 했다가 수정하는 방식으로 나만의 임시저장을 사용해야지.
이처럼 일반적인 형태의 님 게임으로 변형하기 힘든 게임의 경우, 게임판을 어떻게 인코딩할지 생각하는 것이 문제를 푸는 핵심 키가 된다. 만약 인코딩한 결과, 적당히 시간 내에 돌아갈 만한 전이가 있다면 그대로 짜서 내면 되고, 안 될 것 같다면 규칙을 열심히 찾으면 된다.
이 문제의 경우, 행렬에서 각 행은 독립임을 알 수 있다. 따라서, 각 행 하나를 게임판 하나로 보고, 각 행에 대한 grundy number를 구해 모두 xor한 결과를 얻으면 된다는 사실을 관찰하자.
한 행(배열)에 대한 그런디 넘버를 구하는 방식도 별로 다르지 않다. n이 적당히 작고, a[i]의 값들이 적당히 작은 배열을 모두 만들어 보고, 그 과정에서 규칙을 찾아 보면 된다. 예를 들면, N=3이며, 1 <= ai <= 5인 배열은 총 125개밖에 없다.
잘 돌려 보면 다행히 규칙이 매우 쉬운데, 그런디 넘버가 항상 첫 수 A[0]이거나, A[0]-1임을 확인할 수 있다. 어떤 기준으로 변하는지는 첫 수가 연속해서 나온 횟수와, 그 직후 더 큰 수가 나왔는지 아닌지의 여부와 함께 관찰해보면 규칙성을 찾을 수 있을 것이다.
이 게임 또한, 배열에 대한 grundy number를 요구한다. 단, 이 경우엔 게임판이 주어진 배열 하나이므로, grundy number가 0인지 아닌지만 중요하다. 적당히 작은 케이스에 대해 백트래킹 또는 DP를 돌려 보면, 모든 수가 짝수 개 있을 경우 큐브러버가 이기고, 아닐 경우 선공이 이긴다는 사실을 알 수 있다. 믿고 제출하면 AC를 받는다.
어떤 칸 하나를 활성화하면, 그 칸에 L, R이 있었을 경우 새로운 게임판 두 개가 등장하며, X가 있었을 경우 네 개의 게임판이 생긴다. 나뉜 게임판 내에서도 마찬가지로 한 칸을 고르면 4개 이하의 게임판이 새로 생기게 된다. 각 나뉜 게임판의 grundy number을 모두 구해 xor하면 다음 상태의 grundy number를 알 수 있고, 이 값들을 모아 현재 게임판의 grundy number를 계산하는 방식으로 구현하면 된다. '다음 상태' 가 '여러 개의 게임판' 이므로, 나뉜 모든 게임판의 grundy number를 xor해야 다음 상태 '하나' 의 grundy number를 얻을 수 있다는 점에 주의.
근데 나뉘는 영역이 예쁘지 않은 모양이기 때문에 쉽게 구현하기는 힘들다. 이는 처음 배열을 45도 돌려 놓으면, 나뉘는 모든 게임판은 직사각형 영역이 되므로 좌표 두 개로 표현하여 DP를 할 수가 있게 된다.
사실 이 문제의 맞은 사람을 확인하면 내가 없다는 사실을 관찰할 수 있는데, 이유는 비밀이다.
게임판이 한 개인 경우이므로, grundy number가 0인지 아닌지만 중요하다. N이 적당히 작은 경우에 대해 백트래킹해보자. 대충 짜도 N<=7 범위 정도까지는 꽤 빠르게 답을 얻을 수 있다. 결과적으로, N이 홀수일 경우 구사과가 이기고, 짝수일 경우 큐브러버가 이긴다는 사실을 알 수 있다.
문제가 참 복잡하게 생겼다. 그러나 평범한 님 게임임을 확인했다면, 이제 적당히 작은 N에 대해 열심히 돌려서 grundy number를 확인해보자. 그러면 아래와 같은 결과를 얻는다.
어? N=4, 16일 때 수가 바뀐다. 이거는 킹리적 갓심을 안 할려야 안 할 수가 없다. 더 돌려보자. 왠지 N이 64일 때, 256일 때 또 바뀌면 참 좋을 것 같다. 그런디 넘버가 쭉 동일하다가 어느 시점에 1 증가하는 것 같으니, 바뀌는 시점마다만 출력해보도록 하자. 다 풀었다!
라고 생각했는데 바로 망했다. 제곱수거나 제곱수 + 1 꼴에서 변한다는 사실은 알겠는데, 일단 그런디 넘버에 패턴이 없다. 다음 수가 뭔지 궁금해서 더 돌려봐도 나올 생각을 않는다.
한 N <= 1억 정도까지 돌려놓고 몇십 분 기다려서 결과를 봐도 다음 수가 나오지도 않고, 패턴도 잘 모르겠다.
그럼 혹시 N<=10^13일 때, 마지막으로 변한 지점이 50626이 아닐까 하는 희망을 갖고, N=10^13 하나에 대해서만 그런디 넘버를 찾아보자.
얼마나 걸리나 궁금해서 방금 또 짜서 돌려봤는데 대충 1분 30초 정도 돌았다.
근데 일단 망했다. 분명 50626과 10^13 사이 어딘가에서 한 번 이상 그런디 넘버가 변한 것 같다.
다 돌려보기엔 너무 오랜 시간이 걸릴 것이다.
하지만 1억 정도까지는 변하지 않았다는 사실을 알고 있으니, 적당히 1억(10^8)과 10^13 사이의 몇몇 값을 넣어 보자.
그러면 작은 수는 1, 큰 수는 2가 나온다는 사실을 알 수가 있다. 혹시 딱 한 번 변한 게 아닐까? 하는 의심이 든다.
그럼 해야 할 일은 뭘까?
Parametric search다. [10^8, 10^13] 범위에서 값이 처음으로 2가 되는 지점을 바이너리 서치로 찾아본다. 이 작업은 로컬에서 약 10여 분 정도가 소요되며, 이 정도는 기다릴 수 있는 범위 내의 시간이다.
돌려 보면, 2562991876에서 처음으로 grundy number가 2가 된다는 사실을 알 수 있다. (이 값은 long long 범위임에 조심하자)
가장 먼저 관찰해야 할 사항은, 만들 문자열에서 구사과는 가진 문자 중 (N+1)/2개만, 큐브러버는 N/2개만 사용할 예정이라는 것이다. 따라서, 구사과는 가진 문자 중 사전 순으로 가장 앞선 (N+1)/2개만, 큐브러버는 가장 뒷선 N/2개만 갖게 하고 나머지를 다 버리고 시작하자.
구사과의 턴부터 살펴보면, 만약 구사과가 가진 문자 중 단 하나라도 큐브러버가 가진 문자보다 앞선 것이 있다면, 큐브러버가 맨 앞자리에 뒷선 문자를 넣어버리기 전에 반드시 구사과가 맨 앞자리에 가장 앞선 문자를 넣어야 한다.
즉, (구사과가 가진 가장 앞선 문자) < (큐브러버가 가진 가장 뒷선 문자) 라면, 구사과는 가장 앞 자리에 가장 앞선 문자를 넣어야 한다.
만약 그렇지 않을 경우, 구사과는 맨 앞자리를 비워야 한다. 그래야 큐브러버가 언젠가 앞선 문자로 그 자리를 메워 줄 것이다. 따라서, 맨 뒷자리에 문자 하나를 버린다. 그런데 아무 것이나 버리면 안 되고, 가진 문자 중 가장 뒷선 것을 버려야 한다. 그렇지 않을 경우, 가장 뒷선 문자가 결과적으로 들어간 자리와 지금 버린 문자를 스왑하면 항상 사전순으로 더 앞서게 만들 수 있음을 생각해보면 증명된다.
큐브러버의 경우도 비슷하게, 가장 앞 자리에 가장 뒷선 문자를 넣거나, 가장 뒷자리에 가장 앞선 문자를 버리는 식으로 케이스분류하여 진행하면 된다.
우선, 쉬운 문제부터 풀어보자. N은 짝수이고, K = 0이라고 가정하면, 결국 남는 레몬은 무엇일까?
답은 가운데 있는 두 레몬 중 과즙이 많은 쪽이다. 레몬의 배치와 상관없이 항상 그 위치의 두 레몬 중 하나로 결정된다.
그 이유는, 각 플레이어의 목적을 [상대를 어떻게든 방해하는 것]으로 다시 이해하고 보면, 만약 중앙의 두 레몬보다 더 왼쪽에 과즙이 많은 레몬이 있어 구사과가 먹고 싶어한다면, 큐브러버는 그 레몬만은 넘겨주지 않기 위해 왼쪽의 레몬만 다 먹어치워 구사과를 방해할 수 있다. 큐브러버가 원할 경우에도 마찬가지로, 구사과가 다 먹어치워버릴 수 있다.
구사과는 중앙의 레몬 중 왼쪽 레몬을 먹고 싶다면 처음에 오른쪽 레몬을 먹은 뒤 그 다음부터 큐브러버가 먹은 반대쪽 레몬을 먹으면 되고, 오른쪽 레몬을 먹고 싶다면 반대로 하면 된다. 따라서, 가운데의 두 레몬 중 과즙이 많은 쪽이 최종 결과이다.
갑자기 K > 0일 때도 풀렸다. K > 0이라면, N-K 길이의 모든 구간에 대해, 가운데의 두 레몬을 다 합집합해보자. 구사과가 선택할 수 있는 레몬은 연속된 구간으로 나타나므로, max segtree등을 이용해 각 K당 O(logN)에 결과 레몬을 알아낼 수 있다!
이대로 열심히 코딩하면 틀렸습니다!!
그 이유는 N이 홀수일 때 나타난다. N이 홀수라면, 구사과는 정중앙에 있는 레몬을 먹고 싶어도 맘대로 먹을 수 없다.
구사과가 왼쪽 또는 오른쪽 레몬을 먹는 순간, 구간 길이가 짝수가 되며 큐브러버가 선공이 되기 때문이다. 큐브러버는 중앙의 두 레몬 중 과즙이 '적은' 쪽을 택할 것이다.
따라서, 구간의 길이가 홀수라면, 정중앙의 위치를 X라 할 때, max(min(A[X-1],A[X]),min(A[X],A[X+1]))의 과즙을 가진 레몬이 결과가 될 것이다. 이는 B[i] = min(A[i], A[i+1])로 정의한 N-1 길이의 배열 B에 대해 다시 max 세그트리를 만들어 두면 마찬가지로 K 하나당 O(logN)에 결과가 될 레몬을 찾아낼 수 있고, N-K의 홀짝성에 따라 A에서 찾을지, B에서 찾을지를 결정해주면 된다.
개인적으로 이 문제는 굉장히 재밌게 풀었다. 나보다 높은 레벨에서는 웰노운일 듯 싶지만, 나와 비슷한 실력대에서는 상당히 재밌게 풀 수 있는 문제일 듯.
K가 다른 게임들은 따로따로 봐야 할 것 같이 생겼으므로, 각 K마다 그런디 넘버를 행렬 꼴로 출력해 보면 아래와 같은 결과를 얻는다.
행을 0행부터 시작했다고 할 때, 행을 K+1로 나눈 나머지가 K이면 그런디 넘버가 2 또는 3이고, 아닐 경우 적당한 parity 계산으로 그런디 넘버가 0 또는 1이 됨을 확인할 수 있다.
사실 이 문제에서 K를 분리해내고 출력해보면 편하지 않을까, 하는 생각을 너무 늦게 해서 삽질을 오래 했다. i/k와 i, j, (i+j)의 패리티로 열심히 계산해보다가, 지칠 때쯤 K에 따라 행렬꼴로 다시 출력해서 얻은 결과가 이거였다. 이런 건 빠르게 유도해낼 능력 또는 빠르게 관찰해낼 직관 둘 중 하나는 있어야 잘 푸는 문제인 것 같다.
모든 돌무더기를 xor하면 된다. 그러나, 각 채석장에 무려 10^16개의 돌무더기가 있어, 직접 계산하는 것은 어려워 보인다.
우리는 f(N) = 1^2^3^...^N을 빨리 계산할 수 있으면 좋을 것 같다. 이 경우, 각 채석장에서의 grundy number를 f(X+M-1) ^ f(X-1)로 바로 계산할 수 있다.
이는 각 비트별로 계산하면 편한데, 2^k에 해당하는 비트는 2^(k+1)을 주기로 개수의 변화가 동일하다. 이에 착안하여, O(log10^16) 정도에 f(N)을 계산할 수 있다. 그러나, O(1) 에 계산하는 방법도 존재하는데, 이는 각자 생각해 보면 좋을 것 같다.
이로써 모든 문제의 풀이를 다 작성했다!
이 글을 보고 더 많은 사람들이 새로 추가된 게임 문제들을 시도해줬으면 좋겠다. 이 재미를 혼자 느끼기엔 조금 아쉽다.
