IT/백준
[백준] 27512번 증명
지2러
2023. 10. 28. 15:30
단순히 몇 가지 case를 해보게 되면 규칙을 빠르게 찾을 수 있다. 그러나 증명이 필요해 보여서 증명을 하려고 한다. n,m 격자에서 둘 중 적어도 하나가 짝수인 상황과 둘 다 홀수인 상황을 나눠야 한다.
n,m 중 적어도 하나가 짝수일 때는 짝수이기 때문에
|
3
|
4
|
7
|
8
|
|
2
|
5
|
6
|
9
|
|
1
|
12
|
11
|
10
|
여기서 2->3->4->5->6->7->8->9 처럼 왓다갓다 할 수 있기 때문에 존재할 수 밖에 없다. 더 엄밀하게 할려면 귀납법처럼 확장해 가는 식으로 증명할 수도 있긴 하다.
n,m 둘 다 홀수 일때에는 그렇게 단순하지는 않다.
|
3
|
2
|
X
|
|
4
|
1
|
8
|
|
5
|
6
|
7
|
과 같이 하나가 없다. 절대로 모든 칸을 지나갈 수 없다. 1이 꼭짓점 위치에 있을 때, 1이 모서리 위치에 있을 때, 1이 중앙에 있을 때, 이렇게 3가지만 해보면 대칭이나 회전이 성립하기 때문에 모든 칸을 지날 수 없다는 것을 알 수 있다.(다른 좋은 방법이 있을 지 모르겠다.)
여기서 한 방향을 5로 만들면
|
3
|
2
|
|
|
4
|
1
|
14( 8이였던 것)
|
|
5
|
12(6이 였던 것)
|
13(7이였던 것)
|
|
6
|
11
|
10
|
|
7
|
8
|
9
|
6->7->...->11 루트처럼 딱 연결 부분만 확장시킬 수 있다. 이를 귀납적으로 확장시키면 모든 경우에 대해 n*m-1이 된다는 것을 알 수 있다.