Platinum 1
문제 분석
그런디 문제임이 확실하다. 하지만 게임판의 크기가 굉장히 크기 때문에 또 규칙을 찾아야 할 것 같다.
k=1일 때, 2일 때로 나누어서 그런디 수를 적어보자.
- k=1
0101010112323232030101011212323203030101121212320303030112121212
- k=2
0101010110101010012323231031010101201010103102320120130110310210
규칙 찾기 + 풀이
여기까지 찾고나서 풀이가 생각나서 적기 시작했다.
k가 1일때와 아닐때가 다르다.
k=1일 때는 N과 M이 짝수인 경우에 0이다.
아닌 경우에는 조금 다르다.
우선 N%(k+1)=0&M%(k+1)=0 인 경우는 위에서 볼 수있듯 무조건 2,3이 반복된다.
아닌경우는 또 케이스가 나누어 진다.
N/(k+1)과 M/(k+1) 중에 작은 것이 그 수가 포함된 띠이다.
만약 그 작은 수가 짝수라면 0101 이 반복되는 수, 홀수라면 1010 이 반복되는 띠임을 알 수 있다.
고찰
인줄 알았는데 안풀린다..! 뭔가 잘못됐다. 다시 생각해봐야겠다.
여기에서 계속...
풀고 있는 알고리즘 리스트(Platinum V 이상)