[BOJ 25179] 백준 25179번 - 배스킨라빈스~N~귀엽고~깜찍하게~
1. 문제
$25179$. 배스킨라빈스~N~귀엽고~깜찍하게~ (2022 서강대학교 청정수컵 E번)
백준 25179번 - 배스킨라빈스~N~귀엽고~깜찍하게~ (https://www.acmicpc.net/problem/25179)
2. 풀이
처음 게임을 시작한 사람을 선공, 선공이 아닌 나머지 사람을 후공이라 지칭한다. (여기서는 준서가 선공, 준서가 아닌 상대방이 후공이 된다.)
$M=3$ 이라 가정하고 생각해보자.
$N=1$ $\rightarrow$ 선공이 $1$개를 부르게 된다 $\rightarrow$ 후공 승리
$N=2$ $\rightarrow$ 후공 차례에 $1$개가 남도록 선공이 $1$개를 부른다 $\rightarrow$ 선공 승리
$N=3$ $\rightarrow$ 후공 차례에 $1$개가 남도록 선공이 $2$개를 부른다 $\rightarrow$ 선공 승리
$N=4$ $\rightarrow$ 후공 차례에 $1$개가 남도록 선공이 $3$개를 부른다 $\rightarrow$ 선공 승리
$N=5$ $\rightarrow$ 선공이 $1$이상 $3$이하 개를 부르면, $2$이상 $4$이하 개가 남는다. (이는 후공부터 게임이 시작되어 $N$이 $2,3,4$인 경우와 동일하다.) 이때, 후공은 $1$이상 $3$이하 개를 불러서 선공 차례에 $1$개가 남도록 만들 수 있다. $\rightarrow$ 후공 승리
$N=6$ $\rightarrow$ 선공이 $1$개를 불러서 후공 차례에 $5$개가 남도록 한다. 이는 후공부터 게임이 시작되어 $N$이 $5$인 경우와 동일하다. 그럼 후공이 아닌 사람이 승리하게 되며, 이는 곧 선공의 승리가 된다. $\rightarrow$ 선공 승리
$N=7$ $\rightarrow$ 선공이 $2$개를 불러서 후공 차례에 $5$개가 남도록 한다. 이는 후공부터 게임이 시작되어 $N$이 $5$인 경우와 동일하다. 그럼 후공이 아닌 사람이 승리하게 되며, 이는 곧 선공의 승리가 된다. $\rightarrow$ 선공 승리
승리하려면 상대방 차례에 $1$개가 남도록 해야 한다. 그런데, 자기 차례에 할 수 있는 행동은 $1$이상 $3$이하 개수를 부르는 것이다.
따라서 $N$이 $1+1,1+2,1+3$인 경우, 후공 차례에 $1$개가 남도록 선공이 상황을 통제할 수 있다. 그런데, $N$이 $1+4$가 되면, $1$개가 남도록 상황을 통제할 수 있는 권한을 후공이 갖게 된다.
$N$이 $1+4+1$개라면, 선공이 $1$개를 불러서 후공이 통제권을 갖지 못하도록 만들 수 있다. $N$이 $1+4+2,1+4+3$일 때도 마찬가지이다. 그리고, $N$이 $1+4+4$가 되면, 통제권이 바뀐다.
가져갈 수 있는 개수가 $1$이상 $3$이하이기 때문에, 상대가 어느 개수를 부르든 합이 $4$가 되도록 부르는 것이 가능하다. 따라서, $1+4+4..$의 형태에서 시작하는 사람의 반대 사람이 통제권을 갖게 된다.
여기서 $4$는 $M+1$을 의미한다. $1$이상 $M$이하 개수를 부르면, 반대 사람이 합이 $M+1$이 되도록 부르는 것이 가능하기 때문이다.
이 모든 내용을 합치면, $N$을 $M+1$로 나누어서 나머지가 $1$일 경우, 선공이 패배한다는 사실을 알 수 있다. 나머지 모든 경우에 대해서는 선공이 승리한다.
3. 채점 결과
4. 회고
.
댓글남기기