#2502

강채희·2021년 6월 2일
0
post-thumbnail

#2502

문제

풀이

D,K=map(int,input().split())
flag=0
#dl : 첫번째와 두번째 항이 각각 1,1 인 피보나치 수열 = x의 계수가 됨
d1=[1]*(31)
d1[1]=1
for i in range(2,31):
    d1[i]=d1[i-1]+d1[i-2]

#d2 : 첫번째와 두번째 항이 각각 1,2 인 피보나치 수열 = y의 계수가 됨
d2=[1]*(31)
d2[1]=2
for i in range(2,31):
    d2[i]=d2[i-1]+d2[i-2]
    
    
#K는 d1[D-3]*x + d2[D-3]*y의 곱으로 나타낼 수 있다
for x in range(K):
    for y in range(x,K):
        if d1[D-3]*x+d2[D-3]*y==K:
            flag=1
            break
    if flag==1:
        break
        
print(x)
print(y)

이 문제는 피보나치 수열의 응용 버전이다.
D의 첫번째 항이 x라고 하고 두번째 항이 y라고 하자
그러면 세번째 항부터 x+y,x+2y,2x+3y,3x+5y ... 로 들어난다. 이때 x와 y의 계수를 살펴보면 x의 계수는 첫번째 항과 두번째 항이 각각 1,1인 피보나치 수열이고 y의 계수는 첫번째 항과 두번째 항이 각각 1,2인 피보나치 수열이다.

x와 y를 각각의 범위에서 증가시켜보면 떡의 개수와 맞는 x와 y를 찾을 수 있다.

0개의 댓글