2018. 4. 26. 12:16, 알고리즘/BOJ
https://www.acmicpc.net/problem/9660
N이 작을 땐 DP를 이용해서 O(N)으로 풀 수 있지만 N이 굉장히 크기 때문에 O(N)으로 풀 수가 없습니다. 대신 규칙성을 살펴보면, SK CY SK SK SK SK CY가 반복됨을 알 수 있습니다. 이제 이 주기가 참임을 보이면 되는데, 7개 묶음에 대한 귀납적으로 생각하면 참임을 보일 수 있습니다.
'알고리즘 > 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