https://www.acmicpc.net/problem/9270
문제요약
- 게임판에 말이 주어지고 상/하/좌/우 인접한 말이 있으면 건너 뛸 수 있음
- 건너뛰면 발판이 된 말은 사라짐
- 게임판은 무제한이고 말은 n*n 영역에 주어질때 마지막 한개만 남길 수 있을까?
읽고 이해해봐야할 것
- https://www.cut-the-knot.org/proofs/PegsAndGroups.shtml
- https://www.math.utah.edu/mathcircle/notes/2_22_2006.pdf
접근법
- 사실 이론들을 이해하기도 힘들고, 만족하는 상태는 이해하겠는데 만족을 하면 왜 항상 가능한지는 모르겠음
- 두번째 글을 보면서 이해하다가 보니 게임판에 x,y,z를 매핑하는 방법이 이해가 감
- 게임판에 0/1을 잘 칠해볼 수 있음
- 말이 놓여진 곳의 숫자를 더해볼 수 있음 => 일종의 패리티
- 0/1을 잘 칠하면 특정 상태를 유지할 수 있음
- 1 0 1 (sum : 1) =이동=> 1 0 1(sum : 1) (해설. 말이 1, 0 위치에 있을때 1의 말이 0의 말을 건너뛰어서 1의 자리로 가면 0의 말은 사라짐. 이동 전/후의 합을 구해보면 둘다 1)
- 1 1 0(sum:2) =이동=> 1 1 0(sum:2)
- 합이 변하지 않거나, 2씩 줄거나
- 결국 초반의 합이 홀/짝인 것이 정해지면 게임의 상태가 진행되어도 저 값이 변하지 않음 => 패리티
- 확장해서 x, y, z로 게임판에 새겨볼 수 있음
- 앞선 0/1 표현이 x, y, z로 바꾸면서 연산도 정의하고 등등...
- 연산을 점프 후 상태 변환으로 표현하면
- 게임판을 잘 구성하면 x + y = z, y + z = x, z + x = y 로 항상 이동이 발생하도록 구성할 수 있음
- 그리고 x + y + z = e로 정의함. e는 게임판에 존재하지 않음
- 게임판 초반에 말이 놓여진 상태에서 패리티를 확인해 볼 수 있고 이 값은 변하지 않음!
- 무슨말이냐면, 처음 상태가 x + y + ...로 구성된 상태에서 점프 발생(x, y => z)가 발생하면 다음 상태는 z + ... 로 구성이 됨
- 그런데 전과 후는 동일한 상태임
- 그런데 게임이 완료된 상태에서 말은 게임판 어딘가에 놓여지게 될 것임
- 즉 게임이 잘 끝난다면 최종 값은 x/y/z중 하나 일 것임
- 초기 상태가 x/y/z중 하나가 안되면 어떻게 하더라도 게임이 잘 안끝날 것임
- 초기 상태가 x/y/z중 하나면 게임이 잘 끝날것임
- 그런데 여기서 초기 상태를 만족하면 반드시 게임이 잘 끝날 것임 은 증명을 못하겠다
newbieski