[BOJ/2193] 이친수 / DP , 피보나치 수열
# 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로 풀이하는 이유: 어떤 자릿수까지 올 때 그 이전 자릿수의 패턴만 ..
카테고리 없음
2025. 4. 8. 17:23