[BOJ] 9660번: 돌 게임 6

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


N이 작을 땐 DP를 이용해서 O(N)으로 풀 수 있지만 N이 굉장히 크기 때문에 O(N)으로 풀 수가 없습니다. 대신 규칙성을 살펴보면, SK CY SK SK SK SK CY가 반복됨을 알 수 있습니다. 이제 이 주기가 참임을 보이면 되는데, 7개 묶음에 대한 귀납적으로 생각하면 참임을 보일 수 있습니다.


https://github.com/blisstoner/BOJ/blob/master/9660.py

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 9248번: Suffix Array  (0) 2018.04.30
[BOJ] 11585번: 속타는 저녁 메뉴  (0) 2018.04.26
[BOJ] 9661번: 돌 게임 7  (0) 2018.04.26
[BOJ] 1562번: 계단 수  (0) 2018.04.26
[BOJ] 1305번: 광고  (0) 2018.04.26
[BOJ] 1179번: 마지막 조세퍼스 문제  (0) 2018.04.25
  Comments