PS 일지(2021.10.19)

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이다.
아닌 경우에는 조금 다르다.
우선 $\quad N \% (k+1) = 0 \quad\&\quad M\%(k+1) = 0$ 인 경우는 위에서 볼 수있듯 무조건 2,3이 반복된다.
아닌경우는 또 케이스가 나누어 진다.
$N/(k+1)$과 $M/(k+1)$ 중에 작은 것이 그 수가 포함된 띠이다.
만약 그 작은 수가 짝수라면 0101 이 반복되는 수, 홀수라면 1010 이 반복되는 띠임을 알 수 있다.

고찰

인줄 알았는데 안풀린다..! 뭔가 잘못됐다. 다시 생각해봐야겠다.
여기에서 계속...

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

• 게임 이론 (27/103)