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

💡 백준 2193:

각 자릿수 숫자마다 이친수의 개수 규칙을 찾아 DP 탐색

🌱 코드 in Python

알고리즘: Dynamic Programing

n = int(input())
if n == 1:
	print(1)
else:
	dp = [0] * n
	dp[0] = 1 
	dp[1] = 1
	for i in range(2, n):
		dp[i] = dp[i - 2] + dp[i - 1] # '101'로 시작하는 경우 + '100'로 시작하는 경우
	print(dp[n - 1])

이번 문제는 이친수가 자릿수마다 어떤 규칙을 통해 증가하는지 파악하여 DP탐색을 하면 되는 문제였다

이친수는 1이 연속으로 나올 수 없고, 0으로 시작할 수 없기 때문에
1로 시작하며 바로 뒤에 붙는 숫자는 0으로 시작해야 한다
또한 세번째에 오는 숫자는 0일 수도 있으며, 1일 수도 있다

따라서 100-, 101-, 의 경우로 나누어 볼 수 있다

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

이때 100-으로 시작하는 것은 나의 전단계에서 맨처음 숫자 1을 떼고 10-뒤에 붙이면 완성되고,
101-로 시작하는 것은 101-뒤에 나의 전전단계를 그대로 붙이면 완성할 수 있다

따라서 나는 나의 전단계 + 전전단계의 개수의 합이 된다.

🧠 기억하자

1. 오랜만에 DP 풀었더니 어떻게 푸는 거였더라...? 하고 엄청 고민하고 시작했다
   쉬운 문제였는데 쓸데없이 오래 걸림

백준 2193 바로가기