태그:
1과 00타일을 이용해서 만들 수 있는 길이 N의 이진수의 개수를 구하는 문제입니다. 이 문제는 점화식을 세워서 DP로 풀 수 있습니다. 먼저 N=1인 경우 1 하나, N=2인 경우 00, 11로 두 개를 만들 수 있습니다. N=3인 경우는 N=2인 경우에 1을 붙이는 경우와 N=1인 경우에 00을 붙이는 경우의 합으로 생각할 수 있습니다. N=1인 경우에 11을 붙이는 것은 N=2인 경우에 1을 붙이는 경우와 중복이 됩니다. 이제 관계를 찾아보면, 길이 N인 이진수는 길이 N-2인 이진수에 00을 붙이는 경우와 길이 N-1인 이진수에 1을 붙이는 경우이므로 길이 N인 이진수의 개수는 길이가 N-2인 이진수의 개수와 N-1인 이진수의 개수의 합으로 생각할 수 있습니다. 따라서 점화식은 \(a_n=a_{n-1}+a_{n-2},a_1=1,a_2=2\)가 됩니다. 그런데, 이 점화식을 이용하여 조금 다른 방향으로 계산을 진행해보면 \(a_0=a_2-a_1=1=F_1\)이고 \(a_{-1}=a_1-a_0=0=F_0\)임을 알 수가 있습니다. 결국 피보나치 수열인 것입니다! 이 사실에 입각하여 \(a_n=F_{n+1}\)로 쓸 수 있습니다. 따라서 N+1번째 피보나치 수열을 구한 후 이를 출력하면 됩니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| Python 3 | 코드(Github) / 코드(백준) | 2020-03-31 14:08:14 |