| 길이 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 개수 | 1 | 1 | 2 | 3 | 5 |
이런 규칙을 만족한다.
dp[i] = dp[i-1] + dp[i+1]
N = int(input())
dp = [0, 1, 1] + [0] * N
for i in range(2, N + 1):
dp[i] = dp[i-1] + dp[i-2]
print(dp[N])2차원 리스트를 이용하는 방법도 있다.
| 자리수 | 0 | 1 |
|---|---|---|
| 1 | 0 | 1 |
| 2 | 1 | 0 |
| 3 | 1 | 1 |
| 4 | 2 | 1 |
| 5 | 3 | 2 |
규칙을 보면 0으로 끝나면 위에 두 수를 다 더한다.
1로 끝나면 0으로 끝난 경우에만 1이 올 수 있기 때문에 이전에 0으로 끝난 수를 그대로 가져온다.
N = int(input())
dp = list([0, 0] for _ in range(N+1))
dp[1] = [0, 1]
for i in range(2, N + 1):
dp[i][0] = dp[i-1][0] + dp[i-1][1]
dp[i][1] = dp[i-1][0]
print(sum(dp[N]))
smilegate