[알고리즘/백준] 2193: 이친수(python)

길이	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]))