문제
접근
DP 문제이다.
첫번째 자리는 항상 1이 와야한다.
그리고 이전 자리에 1이 나온 경우는 0밖에 올 수 없다.
이전 자리에 0이 나온 경우 0,1 모두 올 수 있다.
이를 정리하면,
i-1번째 자리에 1이 나온 경우, i 번째 자리에는 0밖에 나올 수 없다.
i-1번째 자리에 0이 나온 경우, i 번째 자리에는 0,1 모두 나올 수 있다.
0, 1에 대해 처리해주기 위해 DP를 2차원으로 만들어 줄 것이다.
DP는 n x 2로 만들어 주고, 첫 번째 자리에는 1밖에 못 오기 때문에,
DP(1, 0) = 0
DP(1, 1) = 1
으로 초기화 해준다.
DP(i, j) = i 번째 자리에 j를 사용했을 때 가능한 경우의 수로 정의하겠다.
즉, DP(2, 0)은 2번째 자리가 0일 때 경우의 수이다.
이제 위에서 얘기한 규칙을 적용해보자.
DP(i, 0) = DP(i-1, 0) + DP(i-1, 1) 이 될 것이다.
DP(i, 1) = DP(i-1, 0) 이 될 것이다.
이를 그대로 구현하면 된다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
n = int(input())
dp = [[0] * 2 for _ in range(n+1)]
dp[1][0] = 0
dp[1][1] = 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(dp[n][0]+dp[n][1])