[백준 2502] 떡 먹는 호랑이(Python)

1.아이디어

1번째 날에 호랑이가 떡을 먹은 개수를 a, 2번째 날에 떡을 먹은 개수를 b라고 하자. 그러면 3번째 날에 떡을 먹은 개수는 a+b, 4번째 날에 떡을 먹은 개수는 a+2b, 5번째 날에 떡을 먹은 개수는 2a+3b, 6번째 날에 떡을 먹은 개수는 3a+5b... 이런식으로 계속 진행하여 d번째 날에 떡을 먹은 개수를 구한다.

d번째 날에 떡을 먹은 개수를 pa+qb라고하자. 그러면 pa+qb=k이다. 이는 qb=k-pa와 같다. 다시말해 k-pa은 q로 나누어 떨어져야한다.(i.e. (k-pa) % q == 0) 이러한 k-pa를 구하기 위해, a를 1부터 대입하여 1씩 증가시켜q로 나누어떨어지는지 확인해본다.

2.코드

import sys

d, k = map(int, sys.stdin.readline().rsplit())
first = [1,0]
second = [0,1]
p, q = 0, 0

for i in range(3, d+1):
    p = first[0] + second[0]
    q = first[1] + second[1]
    first = second[:]
    second = [p, q]

a = 1
while True:
    x = p * a
    y = k - x
    if y % q == 0:
        print(a)
        print(y//q)
        break

    a += 1