[BOJ] 2193 - 이친수

풀이

DP 문제입니다. 1번째에는 무조건 1이 오고 2번째부터 0과 1이 나올 수 있는데 1이 두 번 연속으로만 나오지 않으면 됩니다.

dp 변수에 현재 위치가 0일 때와 1일 때의 경우의 수를 각각 저장할 것입니다.

 

현재 위치가 0이라면 이전 자리는 0, 1 두 가지 모두 올 수 있습니다.

따라서 dp [i][0] = dp [i-1][0] + dp [i-1][1] 이 됩니다.

 

현재 위치가 1이라면 이전 자리는 무조건 0이어야 합니다. 

따라서 dp [i][1] = dp [i-1][0] 이 됩니다.

 

출력으로는 현재 위치가 0인 경우의 수와 현재 위치가 1인 경우의 수를 더하여 출력하면 됩니다.

변수

dp [i][0] = i자리에서 0인 경우의 수

dp [i][1] =  i자리에서 1인 경우의 수

 

Python3 Code

n = int(input())

dp = [[0] * 2 for i 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]))