PS 일지(2021.10.27)

16897. 아인타 게임

Platinum 1

문제 분석

그런디 문제임이 확실하다. 하지만 게임판의 크기가 굉장히 크기 때문에 또 규칙을 찾아야 할 것 같다.
k=1일 때, 2일 때로 나누어서 그런디 수를 적어보자.

1. $k=1$
   $\begin{matrix} 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & \textcolor{blue}{2} & \textcolor{blue}{3} & \textcolor{blue}{2} & \textcolor{blue}{3} & \textcolor{blue}{2} & \textcolor{blue}{3} & \textcolor{blue}{2} \\ 0 & \textcolor{blue}{3} & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & \textcolor{blue}{2} & 1 & \textcolor{blue}{2} & \textcolor{blue}{3} & \textcolor{blue}{2} & \textcolor{blue}{3} & \textcolor{blue}{2} \\ 0 & \textcolor{blue}{3} & 0 & \textcolor{blue}{3} & 0 & 1 & 0 & 1 \\ 1 & \textcolor{blue}{2} & 1 & \textcolor{blue}{2} & 1 & \textcolor{blue}{2} & \textcolor{blue}{3} & \textcolor{blue}{2} \\ 0 & \textcolor{blue}{3} & 0 & \textcolor{blue}{3} & 0 & \textcolor{blue}{3} & 0 & 1 \\ 1 & \textcolor{blue}{2} & 1 & \textcolor{blue}{2} & 1 & \textcolor{blue}{2} & 1 & \textcolor{blue}{2} \\ \end{matrix}$
2. $k=2$
   $\begin{matrix} 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & \textcolor{blue}{2} & \textcolor{blue}{3} & \textcolor{blue}{2} & \textcolor{blue}{3} & \textcolor{blue}{2} & \textcolor{blue}{3} \\ 1 & 0 & \textcolor{blue}{3} & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & \textcolor{blue}{2} & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & \textcolor{blue}{3} & 1 & 0 & \textcolor{blue}{2} & \textcolor{blue}{3} & \textcolor{blue}{2} \\ 0 & 1 & \textcolor{blue}{2} & 0 & 1 & \textcolor{blue}{3} & 0 & 1 \\ 1 & 0 & \textcolor{blue}{3} & 1 & 0 & \textcolor{blue}{2} & 1 & 0 \\ \end{matrix}$

규칙 찾기 + 풀이

여기까지 찾고나서 풀이가 생각나서 적기 시작했다.
$k$가 1일 때와 아닐 때가 다르다.
$k=1$일 때는 $N$과 $M$이 짝수인 경우에 0이다.
아닌 경우에는 일단 $(N,M)$이 어떤 띠에 들어가 있는지를 찾는다. 이는 $belt = min(N,M)$으로 구할 수 있다.
그 후, 만약 $bel$t 가 $(k+1)$의 배수라면, 묻지도 따지지도 않고 2,3,2,3이 반복되는 띠이므로 koosaga를 출력한다.
아니라면, $N$과 $M$에서 각각 $belt/(k+1)$을 빼준다.
이후, 만약 $belt/(k+1)$이 짝수일 때와 홀수일 때로 나누어 0101과 1010으로 나누어 계산해주면 된다.

고찰

하... 규칙을 멀쩡히 찾아놓고 구현을 이상하게 해서 틀렸었다.
구현 연습을 좀 더 열심히 해야겠다는 생각이 든다.

풀고 있는 알고리즘 리스트(Platinum V 이상)

• 게임 이론 (28/104)