Code Inside

# 0과 1로만 이루어진 수n = int(input())# n 자리 이친수의 개수dp = [0]*(n+1)dp[1] = 1#이친수는 0으로 시작할 수 없음 (단한가지)if n >= 2: dp[2] = 1# 10 만 가능함 (단한가지)for i in range(3,n+1): # 3자리부터 n자리까지의 이친수 개수를 구할 때까지 반복 dp[i] = dp[i-1] + dp[i-2] # 전형적인 피보나치 수열과 동일한 점화식print(dp[n]) 이친수 조건:0으로 시작 ❌1이 두 번 연속 나오면 안 됨 (11 ❌)이진수만 사용 가능 (0 또는 1)즉, 이친수는 맨 끝이 1이면 반드시 그 앞은 0 이어야 함 이 문제를 DP로 풀이하는 이유: 어떤 자릿수까지 올 때 그 이전 자릿수의 패턴만 ..

#연산 재활용 -> dpX = int(input())dp = [0] * (X+1) # 기본적인 dp 세팅for i in range(2,X+1): dp[i] = dp[i-1] +1 #그리디로 푼다면 짝수, 홀수로 바로 나눌 수 있지만 #이 문제의 경우 경우의 수를 고려하는 최솟값임 if i % 2 == 0: dp[i] = min(dp[i], dp[i//2]+1) # if i % 3 == 0: dp[i] = min(dp[i], dp[i//3]+1) # print(dp[X])