[백준][DP] 1003번 피보나치함수 python (200924)

 

1. 문제설명 

 

 

2. 풀이 

전형적인 DP 문제이다. 

 

원래의 피보나치의 점화식은

DP[idx] = DP[idx-1] + DP[idx-2] 인데,

 

여기서는 약간 변형해서 0과 1의 출력 횟수를 구하는 문제다 

이것도 크게 다르지 않은게  

idx 에서의  0과 1의 출력 횟수는 

idx-1 에서의 0과 1의 출력 횟수  +  idx-2 에서의 0과 1의 출력 횟수 여서 

DP 리스트에 숫자 대신 0과 1의 출력 횟수를 담아주고 dp 리스트를 쌓아나가면 되는 간단한 문제다. 

 

 

하지만 아주 크리티컬한 실수로 시간을 날렸다 ...  DP 초기화 타이밍 이다. 

 

 

 

1) 나의 실수 

import sys
import operator

N = int(sys.stdin.readline())
dp = [(1, 0), (0, 1)]


for _ in range(N): # 입력받는 숫자의 갯수
    num = int(input())

    if num > 1:
        for idx in range(2,num+1):
            dp.append(tuple(map(operator.add,dp[idx-1],dp[idx-2])))
        print(*dp.pop())
    else:
        print(*dp[num])

 

이 코드가 왜 계속 패스가 안되었냐면,

입력 받는 숫자가 바뀌면 dp 를 다시 초기화 시켜주어야 하기 때문에

dp 선언이 for 문 안에 들어갔어야 했던 것이다...

 

 

2) 정답 정답 

import sys
import operator

N = int(sys.stdin.readline())



for _ in range(N): # 입력받는 숫자의 갯수
    num = int(input())
	dp = [(1, 0), (0, 1)]
    
    if num > 1:
        for idx in range(2,num+1):
            dp.append(tuple(map(operator.add,dp[idx-1],dp[idx-2])))
        print(*dp.pop())
    else:
        print(*dp[num])

 

 

설명을 덧붙이자면,

operator.add,dp[idx-1],dp[idx-2])  이 부분은 튜플 요소합이 이뤄지는 거다 

(1,0)  (0,1) ==> (1,1) 로 ! 

(1,0)  + (0,1) 로 하게되면 concat 이 되어 (1,0,0,1) 이 되어버리기 때문에 저 메소드를 써줘야 한다. 

 

그리고 출력되는 형태는 튜플이 아니라 숫자 각각 반환되어야 하기 때문에 

print안에 * 를 넣었다. 

 

 

 

3. 정리 

DP 리스트 initialize 하는 타이밍 제대로 살피면서 코드짜기