[Python] 백준 2193번: 이친수 풀이

 

소스코드

n = int(input())
# dp 초기화
#dp[i][j] 에서 i는 자리수, j는 끝에 오는 수
dp = [[0]*2 for _ in range(n+1)]
dp[1][1] = 1
for i in range(2, n+1):
    dp[i][0] = sum(dp[i-1])
    dp[i][1] = dp[i-1][0]
print(sum(dp[n]))

 

1자리 -> 1 (1가지)

2자리 -> 10 (1가지)

3자리 -> 101, 100 (2가지)

 

이번 문제도 마찬가지로 수의 끝자리에 따라 케이스를 나눌 수 있다.

dp[i][0] 은 i자리수에서 0으로 끝나는 이친수의 개수이다.

dp[i][1] 은 i자리수에서 1로 끝나는 이친수의 개수이다.

dp[i] 는 dp[i][0] + dp[i][1] 로 정의할 수 있다.

 

예를 들어

1) dp[n][0] : n자리에서 끝자리가 _____0 이라고 하자. 0 앞에는 1 이나 0이나 둘다 와도 상관이 없기 때문에 이는

dp[n-1][0] + dp[n-1[1] 과 같다.

반면,

2) dp[n][1] : n자리에서 끝자리가 _____1 이라고 하자. 1 앞에는 0밖에 올 수 없기 때문에 이는 dp[i-1][0] 과 동일하다.

 

그리고 dp[n] 은 이 둘의 합이다.