백준 파이썬 2193 이친수

 

🚀접근하기

이전 다이나믹 프로그래밍 문제에 큰 충격을 받아, 다른 다이나믹 프로그래밍 문제를 하나 더 풀어보았다.

먼저 N = 1 인 것부터 시작해서 일정한 값까지 쭉 써봤는데, N = 6까지 써보니 규칙이 보였다.

윗 그림과 같이 1뒤에 다 0일 때,

1이 일의자리수에 나타날 경우 -> N=1 개수,

1이 십의자리수에 나타날 경우 -> N=2 개수,

1이 백의자리수에 나타날 경우 -> N=3 개수,

.

.

.

임을 알 수 있다.

예를 들어 N = 6일 때,

1뒤에 다 0인 경우(1개) + 1이 일의자리수에 나타날 경우 -> N=1 개수 (1개) + 1이 십의자리수에 나타날 경우 -> N=2 개수 (1개) + 1이 백의자리수에 나타날 경우 -> N=3 개수(2개) + 1이 천의자리수에 나타날 경우 -> N=4 개수(3개) = 8 이다.

 

이를 바탕으로

arr[3] = 1 + arr[1],

arr[4] = 1 + arr[1] + arr[2],                           = arr[3] + arr[2]  

arr[5] = 1 + arr[1] + arr[2] + arr[3],               =arr[4] + arr[3]

arr[6] = 1 + arr[1] + arr[2] + arr[3] + arr[4],   =arr[5] + arr[4]

.

.

.

즉 N = 4 부터 arr[n] = arr[n-1] + arr[n-2] 인 점화식을 세울 수 있다! 

🎉코드

N = int(input())

arr = [0]*(N+1)

arr[1] = 1 #1
if N>=2:
    arr[2] = 1 #10
if N>=3:
    arr[3] = 1 + arr[1] #101, 101

for i in range(4, N+1):
    arr[i] = arr[i-1] + arr[i-2]  

print(arr[N])

일정한 규칙과 점화식을 세운 이후, 이를 코드로 작성하는 건 어렵지 않았다.

하지만 이 문제도 이전 다이나믹 프로그래밍 문제와 같이 index error를 방지하기 위해 if 문들을 작성해 주었다. 

 

💪다짐

규칙과 점화식을 찾아내는 과정이 생각보다는 재밌었던 다이나믹 프로그래밍 문제였다.

 

다이나믹 프로그래밍 문제는 묘한 매력이 있는 것 같다.

 

다이나믹 프로그래밍 문제를 여러개 더 풀어보면서 완전히 감을 잡아야겠다!