2502 백준 파이썬

실버 1이 무색할 정도로 정석적인 dp문제가 아니었나..

 

첫 입력값을 d1, 두번째 입력값을 d2라고 하자.

D(3)=d1+d2

D(4)=D(3)+D(2)

D(5)=D(4)+D(3)

으로 분해 할 수 있다.

따라서 일반항은

 

D(n)=D(n-1)+D(n-2)

그러면 결국 예제 입력 [6, 41]에 대해서

 

D(6)=D(5)+D(4)=......3d1+5d2=41이라는 식을 갖게 된다.

d1에 대입을 하다 보면 d1=2, d2=7이 된다.

 

나는 전역 변수를 통해 d1, d2를 세주고, 방정식의 해가 나올 시에 바로 출력을 끝내게 만들었다.

import sys
sys.setrecursionlimit(100000)
d,k=map(int,input().split())
d1,d2=0,0
def dp(n):
    global d1
    global d2
    if n==1:
        d1+=1
        return 
    if n==2:
        d2+=1
        return 
    else:
        dp(n-1)
        dp(n-2)
dp(d)
for x in range(k//d1):
    for y in range(x,k//d2):
        if x*d1+y*d2==k:
            print(x)
            print(y)
            exit()