새싹프로그래머의 이야기

https://www.acmicpc.net/problem/2193

문제: 정수 N이 주어졌을 때, N자리 이친수의 갯수를 구하는 문제

풀이 방법: DP

풀이 코드:

n = int(input())

dp = [0] * (n+1)

dp[1] = 1

if n > 1:
    dp[2] = 1
    for i in range(3,n+1):
        dp[i] = dp[i-1] + dp[i-2]

print(dp[n])

풀이 설명:

이 문제는 규칙성이 눈에 보여서 점화식으로 간단하게 해결 할 수 있었습니다.

먼저 조건은 다음과 같습니다.

1. 첫번째 자리는 무조건 1 이어야 한다.

2. 1이 연속되게 나올 수 없다.

즉, N = 1일 때는 1만 가능하며 N = 2일 때 또한 10만 가능하다는 것입니다.

N = 3 이라면, 3번째 자리 수에는 0 또는 1이 올 수 있으므로 경우의 수는 2가지 입니다.

N = 4 라면, 3번째 자리 수가 0일 경우 4번째 자리 수에 0 또는 1이 올 수 있으며 세번째 자리 수가 1일 경우 0만 올 수 있습니다.

이를 도식화 하면 다음과 같습니다.

N = 3일 때는 0 , 1  두가지 경우의 수가 있습니다.

N = 4일 때는 N = 3 일 때 기준으로 0 - 0 , 0 - 1, 1 - 0 으로 이어지는 3가지 경우의 수가 있죠.

N= 5일 때는 그림과 같이 5가지 경우의 수, N =6일 때는 8가지 경우의 수가 생깁니다.

즉, 여기서 하나의 점화식을 구할 수 있었죠.

F(x) = F(x-1) + F(x-2) (x >= 3) 입니다.

따라서, 다음 점화식을 통해 문제를 간단하게 해결 할 수 있었습니다.