[백준] 2193: 이친수 (Python)

문제📖

풀이🙏

• dp[자리수][뒤에 오는 수]를 이용하여 2차원 dp 테이블을 생성한다.
• 뒤에 오는 수가 1 일 경우에는 이전에 1이 나오면 안되므로 이전까지 0 이 오는 dp[i-1][j-1]로 초기화한다.
• 뒤에 오는 수가 0 일 경우에는 0과 1이 둘 다 이전에 와도 상관 없으므로 dp[i-1][j+1] + dp[i-1][j] 로 초기화한다.

코드💻

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):
    for j in range(2):
        if j == 1:
            dp[i][j] = dp[i-1][j-1]
        else:
            dp[i][j] = dp[i-1][j+1] + dp[i-1][j]

print(sum(dp[n]))