[백준][python]2193 이친수

문제

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

소스코드

if __name__ == "__main__":  
    n = int(input())
    dp = [1 for _ in range(n+1)]

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

설명

- DFS로 완전탐색으로 하니 n이 커지니까 시간초과 발생함.

- 중복되는 부분을 메모이제이션해서 풀어준다.

 

- DP로 풀 때 확인해야할 점
1. 전체를 부분으로 나눈다.
2. 뭘 메모이제이션 해야할지 확인한다. (우리가 구해야할 값: n자리수 이친수)
3. 부분을 점화식으로 만들고 모든 관계가 체크 되었는지 확인한다.

 

n일 때의 이친수의 갯수를 구해야하니 n이 1일 때 부터 차근차근 생각해본다.

n=1 1
n=2 10
n=3 100, 101
n=4 1000,1001,1010
n=5 10000,10001,10010,10100,10101

이렇게 하나하나 생각해봤을 때
n = 1인 경우는 무조건 1이다. >1
n = 2인 경우는 1일 때 1이니까 0밖에 못와서 10 >1
n = 3인 경우는 2일 때 10일 때 뒤에 0하고 1이 올 수 있어서 2 > 1+1
n = 4인 경우는 3일 때 (100은 뒤에 0하고 1이옴)2가지 +(101은 0만 옴) 1가지 > 2+1
n = 5인 경우는 4일 때 (1000은 뒤에 0하고 1이옴)2가지 + 1 + 2 > 2 + 1 + 2
이렇게 귀납적으로 보다보면 dp[i] = dp[i-1] + dp[i-2] 인 것을 확인할 수 있다.

 

후기

dp = [0] * (n+1) 로 설정해주고

dp[1] = 1 

dp[2] = 1

이렇게 초기화를 해주면  n = 1 일 때 인덱스 오류가 발생한다.

 

초기화를 처음부터 1로 다해주면 된다.