fibonacci
-
[BOJ] 1904 01타일PS/BOJ 2020. 7. 16. 19:37
https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이�� www.acmicpc.net 알고리즘: DP, Math (Fibonacci number) 시간복잡도: 1. O(N) 2. O(p) (p = 47244, Pisano Period) 접근: 1. 1, 00 타일로 만들 수 있는 길이가 N인 수열의 모든 가짓수 2. 타일을 붙여서 점점 길이를 확장 (부분문제) -> 1, 2번 조건을 통해 Dynamic으로 접근할 수 있음을 알 수 있다. D[N]: 길이가 N인 수열을 만들 수 있는 ..