백준 2502(떡 먹는 호랑이) - Python(파이썬) - 다이나믹프로그래밍

2502번: 떡 먹는 호랑이

접근방법

일단 1, 2, 3, 5 이런식으로 증가하기 때문에 피보나치 수열인 것을 안다.

이걸 문자로 표현하여서 첫째와 둘째를 A와 B라고 가정하면 밑의 표와 같이 증가한다.

1	2	3	4	5	6	7
A	B	A+B	A+2B	2A+3B	3A+5B	5A+8B

이걸 A의 계수 관점, B의 계수 관점으로 분리하면

A의 계수 관점(dpA)

1	2	3	4	5	6	7
1	0	1	1	2	3	5

B의 계수 관점(dpB)

1	2	3	4	5	6	7
0	1	1	2	3	5	8

따라서 이 계수를 이용하여서 D번째에 있는 A의 계수, B의 계수를 이용해서 방정식이 만들어진다고 볼 수 있다

dpA[D] *A + dpB[D] *B = K

이때의 A,B의 값은 하나 이상일 경우 하나만 구하면 된다.

 

이 방법으로 D = 6, K = 41일 때 dpA[6] = 3, dpB[6] = 5가 나온다.

3A + 5B = 41인 A,B의 값을 구한다.

이제 41을 5로 나눈 몫은 8이다. 8을 기준으로 하나씩 빼가면서 성립되는 A의 값을 구한다.

① B = 8 -> 41- 5*8  = 1 인데 3으로 나누어 지지않음 (X)

② B = 7 -> 41 - 5*7 =6 이므로 3으로 나누어지므로 A = 2 ( O ) 

 

출력방법
① dpA,dpB를 (D+1)로 설정 ( 이유 : 인덱스와 몇번째인지 일치하게 만들기 위해서 인덱스 0을 임의로 만든다)
② dpA[1], dpB[2] 에 1로 설정, dpA[2], dpB[1] 을 1로 설정
③ 피보나치수열을 첫번째,두번째를 제외하므로 인덱스 3부터 시작해서 구함
④ 몫 K//dpB[D]을 구한 뒤에는 하나씩 빼면서 while 루프 돌린다. 이 때 (K-dpB[D]*몫)가 A로 나누어지고 이때 구한 A의 값이 0보다 크면 while문 그만하기

import sys
D,K = map(int,sys.stdin.readline().split())
dpA=[0]*(D+1)
dpB=[0]*(D+1)
dpA[1]=dpB[2]=1
dpA[2]=dpB[1]=0
#피보나치수열로 A의 계수, B의 계수 출력
for i in range(3,D+1):
    dpA[i]=dpA[i-1]+dpA[i-2]
    dpB[i]=dpB[i-1]+dpB[i-2]

#B의 최댓값
i=K//dpB[D]
while i>0:
    #하나씩 줄기
    i+=-1
    #K에서 B*몫을 뺀 값이 A로 나누어지고 A>0이면
    if (K-dpB[D]*i)%dpA[D]==0 and (K-dpB[D]*i)//dpA[D]>0:
        break

print(int((K-dpB[D]*i)/dpA[D]))
print(i)