[백준] 2193 - 이친수 [Python(파이썬)]

문제

www.acmicpc.net/problem/2193

2193번: 이친수

풀이

이전에 풀었던 오르막 수 문제의 쉬운 버전 문제다.

dp[n][0] = 0으로 끝나는 n자리 이친수의 개수

dp[n][1] = 1로 끝나는 n자리 이친수의 개수

 

문제에 주어진 조건을 살펴보자.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

1번 조건에 의해 dp[1][0] = 0, dp[1][1] = 1이 성립한다.

2번 조건에 의해 dp[n][1] = dp[n-1][0]이 성립한다. 0으로 끝나는 n-1자리 이친수는 n번째 자리에 1밖에 올 수 없기 때문이다. 

 

정리하면 점화식은 다음과 같이 표현할 수 있다.

dp[n][0] = dp[n-1][0] + dp[n-1][1]

dp[n][1] = dp[n-1][0]

 

이 문제는 경로의 개수를 구하는 문제에도 응용해볼 수 있을 것 같다. 

 

코드

import sys

n = int(sys.stdin.readline().strip())
dp = [[0 for _ in range(2)] for _ in range(n+1)]
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(sum(dp[n]))