[diamond4] [해설안봄,분류안봄,반례확인] 18939 경비병 세우기 게임

알고리즘/baekjoon(boj)

[diamond4] [해설안봄,분류안봄,반례확인] 18939 경비병 세우기 게임

끄응끄응 2025. 10. 4. 03:23

https://www.acmicpc.net/problem/18939

이 문제는 처음에 발상은 매우 재미있게 했지만.. 나중에 반례 찾는데 정말 스트레스를 받았던 문제다..

반례 찾는데 빠지는 내 머리카락에 대한 기회비용이 아깝기 때문에 반례를 확인해 논리적으로 납득해 수정해 풀었다.

최선을 다해 플레이 한다는 생각이 참신하고 재밌었다.

우선 최선을 다해 플레이 한다는 개념에 익숙해 지기 위해 1차원적으로 생각해 보았다.

이렇게 너비(M)은 생각하지 말고 생각해보자

yuto가 이번 줄은 자기가 마지막으로 끝내고 싶다고 해보자.

자리3에 경비병을 두면 한번만에 끝낼 수 있다.

이번엔 yuto가 platina로 끝내게 하고 싶다고 하자. 그게 가능할 것인가?

yuto가 자리1에 배치하면, platina는 자리3,4,5 에 두는 순간 끝날 것이다. 아니면 platina는 자리 2에 둘 수도 있다. 만약 자리2에 두게된다면 yuto는 3,4,5 중 하나에 두어야 하고 yuto로 끝나게 된다.

yuto가 자리2에 배치해도, platina: 자리1 -> yuto:자리3or4or5 로 yuto로 끝나거나 platina: 자리3or4or5 로 platina로 끝날 수 있다.

즉 선택권은 platina가 가지고 있는 셈이다. '

즉 yuto는 자기 마음대로 platina로 끝내게 할 수는 없다. 그러나 무조건 yuto로 끝나게 할수는 있다.

즉 n= 5, k= 3 일때는 yuto와 platina모두 마음만 먹으면 무조건 yuto로 끝나게 할수는 있지만 무조건 platina로 끝나게 할수는 없다. platina가 platina로 끝나게 하고 싶어도 yuto가 마음만 먹으면 불가능 하고, yuto가 platina로 끝나고싶어도 platina가 방해할 수도 있다.

N = 7 , K = 4 인 경우를 생각해보자.

Y의 목표 : Y로 끝내기 -> 성공

P의 목표 : P로 끝내기 -> 실패

Y의 목표는 자리 4에 둠으로써 바로 달성이다. P의 목표는 실패로 끝나버렸다.

다음목표는 다음과 같다.

Y의 목표 : P로 끝내기 : ->성공

P의 목표 : Y로 끝내기: -> 실패

4에 y를 놓으면 바로 끝나버리므로, y는 적당한 5정도에 두려할 것이다. P는 Y로 끝내야 하므로 4에서 떨어진 6 or 7에서 버티려 할 것이다. y또한 4에 두면 y로 끝나버리므로 6 or 7 에서 버티려 할 것이다. 이제 6 or 7의 자리는 풀방이므로 어쩔수 없이 p가 1or2or3or4 의 자리로 간다.

단, Y의 목표와 P의 목표가 같은 경우는 있을 수가 없다. 서로 각자 이기기 위해 선택을 해야 하는데 같은 목표를 둘 수는 없기 때문이다.

N = 7 에서는 y의 목표가 y로끝내기든 p로 끝내기든 모두 성공시킬 수 있다. 즉 먼저 자리를 선점하면 상당히 유리한 것이다.

N= 8 에서도 살펴봅시다.

Y의 목표 : Y로 끝내기 -> 실패

P의 목표 : P로 끝내기 : -> 성공

N = 7에 비해 1자리가 더 늘었으므로 한칸을 더 채워야 하기 때문에,

Y의 목표는 실패로 끝날 것이고, P의목표는 성공으로 끝날 것이다.

Y의 목표 : P로 끝내기 -> 실패

P의 목표 : Y로 끝내기 ->성공

이것또한 마찬가지로 Y는 실패로, P는 성공으로 끝날 것이다.

한자리가 더 생겼기 때문에 N = 7에서 성공할 것이 실패로, 실패할 것이 성공하는 것이 된다.

따라서 N = 8 에서는 자리를 나중에 선점하는 것이 유리하다.

한자리의 생김으로 인해 계속 결과가 뒤바뀌므로,

N = 홀수일때는 선점,

N = 짝수일 때는 후점이 유리하다.

단 예외케이스가 있다. N < = 2 *K - 1, 즉 한 경비병만으로 다 범위를 채울 수 있는 경우는 무조건 선점하는 사람이 한줄을 끝낼 수 있다.

이제 K = 3인 경우도 해봅시다.

N = 2 * 3 - 1 =5 부터 해보면

Y의 목표 : Y로 끝내기 -> 성립

P의 목표 : P로 끝내기 -> 실패

Y의 목표 : P로 끝내기 -> 실패

P의 목표 : Y로 끝내기 -> 성공

N = 6일때는

Y의 목표 : Y로 끝내기 -> 실패

P의 목표 : P로 끝내기 -> 성공

Y의 목표 : P로 끝내기 -> 성공

P의 목표 : Y로 끝내기 -> 실패

정리하면 이렇다

K \ N 홀수 짝수

홀수 Y:Y P:P

P:Y Y:P

짝수 Y:Y P:Y

Y:P P:P

Y:P 는 Y가 P로 끝나게 하는데 성공

유의해야 할 점이 한가지 있다.

Y로 시작했을 때 Y로 끝나는 경우는 Y가 Y로 끝내기로 마음먹거나, P가 Y로 끝내기로 마음먹었을 때 반드시 Y로 끝낼 수 있는 경우다. 만약 Y는 P로 끝내고 싶었는데 P가 Y로 끝내거나, 그 반대의 경우는 고려하지 않는다.

고려대상:

Y: Y로 무조건 끝내겠어 -> 성공

P: Y로 못끝내게 방해하겠어. -> 실패

P: Y로 무조건 끝내겠어 -> 성공

Y: Y로 못끝내게 방해하겠어 -> 실패

다음과 같은 경우는 고려하지 않는다.

비고려대상

Y: Y로 무조건 끝내겠어

P : Y 또는 P로 마음대로 끝낼 수 있는데 Y로 끝내야지

그 이유는 각 선수는 최선을 다해 이기기 위해 노력하는데, Y가 Y로 끝내려 한다면, 무조건 Y로 끝내는게 Y의 승리에 한발자국 기여하기 때문이다. 그런데 P도 Y로 끝내려 한다는 건 Y에 승리에 도움이 되는거므로 있을 수 없다,

다음과 같은 경우는 OK

Y: Y로 무조건 끝내겠어 -> 실패

P: Y로 끝내면 Y한테 이득이니 나는 무조건 P로 끝내겠어 -> 성공

이 경우에는 직접 해보면 다음과 같은 경우도 성립함을 알 수 있다.

Y: P로 무조건 끝내겠어 -> 성공

P : P로 끝내면 Y한테 이득이니 나는 무조건 Y로 끝내겠어 -> 실패

이부분까지 인지를 했으면 다음을 살펴보자

1. N = 짝수 일 때 -> M과 상관 없이 P가 승리

다음과 같이 한줄마다 Y로 시작하면 P로 끝날 경우 끝나는 지점까지 쭉 가면 P로 끝난다.

2. N = 홀수 일때 -> M이 홀수이면 Y, 짝수이면 P가 승리

위는 M이 홀수인 경우이고, 끝나는 라인에서 Y로 승리.

그러나 이것은 잘못된 생각이었다..

다음과 같은 상황에서 P로 시작해 P로 끝나는 줄 다음줄의 상황에 있다고 해보자. y로 시작하는데 p가 순순히 y의 의도대로 이 초록줄에 배치를 해 나가면 결국 y가 이길 건데, 과연 순순히 이기게 둘까? 그렇지 않을 것이다. p는 어떻게든 저 초록줄에 안들어가려고 공백 부분에서 버티려고 할 것이다.

여기서 재밌는 발견이 있다. p가 공백 부분에서 버티려 할 동안 y는 어떻게 배치를 할까? 우선 절대로 하지 않을 행동은 마지막 줄에 계속 배치를 하는 거다. 그 이유는만약 p가 공백부분을 채우는동안 마지막 줄을 계속 채운다면, y가 계속 미지의 곳(초록 줄)에 배치를 해나가는 동안 p는 공백부분을 채워나가며 버티며 기회를 엿보다가 딱 한번만 더 배치하면 마지막 줄까지 전부 채우게 될 순간에, 치고 나와서 마지막 깃발을 차지하며 승리해 버릴 것이다. 따라서 p가 공백에서 버티기 전략을 택해버리면 y도 똑같이 미지의 곳을 채우지 않고 공백을 같이 채워나가는 선택지 밖에 없다.

꼭 마지막 줄이 아니더라도, p가 버티기전략을 하는동안 y가 다른 곳에 깃발을 꽂는 행동은 절대로 하지 말아야 한다. y가 깃발을 다른 곳에 전개하는 동안, p는 계속 차곡차곡 이전의 줄에서 공백부분을 쌓아가며 버티다가 자기가 유리한 순간이 올때 치고 나올 수 있기 때문이다.

그렇다면 y와 p모두 차곡차곡 쌓아가면 결말은 어떻게 될 것인가

다음과 같은 상황에 y와 p 모두 차곡차곡 쌓아 나가다가 마지막 결정을 짓는 부분(마지막 줄)에서 더이상 다른 채울 공백이 없을 때 이제 y는 마지막줄에서 y로 시작하게 되고, 필연적으로 y로 끝나게 된다.

사실 다음 시나리오가 더 자연스러울 것이다.

한 줄이 p, y, p 로 끝난 다고 생각해보자.

2번째 줄에서 p -> y -> p 에서 이미 이번줄은 다 채워졌고, y가 버티기 위해 계속 2번째줄에서 채워나가려 하는데, p가 기회를 엿보고 3번째줄에 깃발을 꽂았다.(1번) P로 시작하면 P로 끝낼수 있다고 생각했기 때문일 것이다. 이대로 차곡차곡 쌓아나가면 3번째줄은 y로 시작하게 되어 p는 필패하게 되므로, 야심찬 공격이라고 볼 수 있다.

그러나 y는 아랑곳하지 않고 2번째 줄에서 차곡차곡 버틴다. (2번) 그러자 p는 계속 미지의 곳에 깃발을 꽂으면 자기에게 손해라는 것을 알기 때문에 어쩔 수 없이 다시 두번째 줄로 돌아가 깃발을 꽂는다. (3번)

5번째 순서로, p는 이제 어쩔수없이 3번째줄로 돌아가야 한다. 그러나 이미 한번 깃발을 꽂아었기 때문에, 이 상태로 돌아가면 자신은 필패하게 된다.

(P -> Y -> P 로 끝나든 P -> P -> Y 로 끝나든 Y-> P->Y로 끝나든 깃발만 채워지면 된다).

즉 p는 최선을 다해도 어쩔 수 없이 지게 되는 것이다.

(추가. 만약 차곡차곡 공백에 쌓다가 Y가 다른 좋은 수를 발견해 다른 곳에 깃발을 꽂으면 어떨까? P는 그대로 차곡차곡 쌓기만 하면 된다. 왜 그럴까? Y가 좋은 수를 발견해 깃발을 꽂았다 한들, 다른 쪽이 반응을 안해주면 말짱도루묵이기 때문이다.

아래와 같이 y가 다른곳에 좋은 수를 발견해 이탈했다고 치자(파란색) P는 그대로 차곡차곡쌓으면 Y는 다시 돌아올 수 밖에 없다. 파란색쪽에 자기가 유리한 세팅을 했지만 P가 그쪽줄에 같이 쌓지않는다면, Y는 다시 공백에서 버틸수밖에 없다 . 왜냐하면 이미 세팅해놓은 자리에 자기가 한번 더 배치하는 순간, P에게 유리한 줄이 되버리기 때문이다. 한칸씩 늘어나거나 줄어들때마다 유리한 플레이어가 뒤바뀌는 성질때문에 그렇다. 결국 파란색Y를 제외한 곳에서 같이 공백을 채우다보면 Y는 7개, P는 8 개로 이탈하지 않았으면 채웠을 양상과 동일하게 채우게 된다)

이제 일반적인 경우로 돌아가보자.

N 이 짝수인 경우, 무조건 P가 이긴다는 것을 확인하였다.

다음과같다.

왼쪽부터 차곡차곡 쌓는다고 가정했을 때, 위와 같다.

N 이 짝수일 때 무조건 후점하는게 유리하다고 했으므로, 서로 필사적으로 마지막줄에 안들어가려고(초록색줄) 노력할 것이다.

그러다 N은 짝수이므로 1~ m-k 줄까지 채웠을 때 p로 끝나게 될것이다. 그 이후 과정은 뒤에서 설명한다.

이제, N 이 홀수일때를 생각해보자.