문제

하루에 한 번 산을 넘어가는 떡 장사 할머니는 호랑이에게 떡을 주어야 산을 넘어갈 수 있는데, 욕심 많은 호랑이는 어제 받은 떡의 개수와 그저께 받은 떡의 개수를 더한 만큼의 떡을 받아야만 할머니를 무사히 보내 준다고 한다.

예를 들어 첫째 날에 떡을 1개 주었고, 둘째 날에는 떡을 2개 주었다면 셋째 날에는 1+2=3개, 넷째 날에는 2+3=5개, 다섯째 날에는 3+5=8개, 여섯째 날에는 5+8=13개를 주어야만 무사히 산을 넘어갈 수 있다.

우리는 산을 무사히 넘어온 할머니에게 오늘 호랑이에게 몇 개의 떡을 주었는지, 그리고 오늘이 호랑이를 만나 떡을 준지 며칠이 되었는지를 알아내었다. 할머니가 호랑이를 만나서 무사히 넘어온 D째 날에 준 떡의 개수가 K개임을 알 때, 여러분은 할머니가 호랑이를 처음 만난 날에 준 떡의 개수 A, 그리고 그 다음 날에 호랑이에게 준 떡의 개수 B를 계산하는 프로그램을 작성하시오. 이 문제에서는 항상 1≤A≤B 이다.

예를 들어 여섯 번째 날에 산을 무사히 넘어온 할머니가 호랑이에게 준 떡이 모두 41개라면, 호랑이를 만난 첫 날에 준 떡의 수는 2개, 둘째 날에 준 떡의 수는 7개이다. 즉 셋째 날에는 9개, 넷째 날에는 16개, 다섯째 날에는 25개, 여섯째 날에는 41개이다. 따라서 A=2, B=7 이 된다. 단 어떤 경우에는 답이 되는 A, B가 하나 이상일 때도 있는데 이 경우에는 그 중 하나만 구해서 출력하면 된다.

입력

첫째 줄에는 할머니가 넘어온 날 D (3 ≤ D ≤ 30)와 그 날 호랑이에게 준 떡의 개수 K (10 ≤ K ≤ 100,000)가 하나의 빈칸을 사이에 두고 주어진다.

출력

첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤A≤B)가 존재한다.

문제의 조건을 보라. ‘피보나치 수’다. 앞선 두 숫자의 합이 해당 숫자가 되는 규칙. (0, 1, 1, 2, 3, 5, 8, 13, …) 문제는, 첫째 날과 둘째 날 할머니가 호랑이에게 준 떡이 0과 1이 아니라는 점. 이 첫 번째와 두 번째 숫자에 따라 다음 숫자들이 정해진다. 이 두 수를 구하는 게 이번 문제. (스페셜 저지 문제로, 답이 여러 개일 수 있다.)

규칙을 찾아서 점화식을 구하는 게 가장 먼저 할 일이다. 늘 그렇지만.

첫째 날 준 떡의 수를 a, 둘째 날 떡의 수를 b라고 하자. 첫 날부터 하루가 지날 때마다 할머니가 호랑이에게 줘야 할 떡의 수는 다음과 같다.

[a, b, a+b, a+2b, 2a+3b, 3a+5b, 5a+8b, 8a+13b, ...]

숫자 n이 주어졌을 때, n번째 피보나치 수를 구하는 식은 아래와 같다. (참조)

def fibo(n):
	x = 1
	y = 0
	for i in range(n-1):
    	x, y = y, x+y
	return y # y가 n번째 피보나치 수

예문대로, 6번째 날 호랑이가 먹는 떡의 수를 보자. 3a+5b개. 즉, fibo(5)*a + fibo(6)*b다.

요컨대, d번째 날 호랑이가 먹는 떡의 수는 `fibo(d-1)*a + fibo(d)*b`개다.

위 피보나치 함수에 따라 d번째 날 호랑이가 먹을 떡의 수를 구하는 식을 세워 보자.

for i in range(d-1):
    x, y = y, x+y
k = ax + by

d번째 날 먹은 떡의 수(k)는 첫째 날 먹은 떡(a) * x와 둘째 날 먹은 떡(b) * y를 합한 값이다. 여기서 중요한 건 첫째 날과 둘째 날 먹은 떡 a, b를 구하는 것이다. d만 주어지면 x, y는 구할 수 있고, 마지막 날 먹은 떡의 수 k도 주어진다. 그렇다면 a는 1부터 차례대로 넣으면서 k = ax + by가 성립되는 b를 찾으면 반복문을 종료하면 될 일.

다시 위 식을 보자.

k = ax + by이므로, ${b}={\frac{k-(a*x)}{y}}$이다.

그럼 a를 1부터 오름차순으로 차례로 넣으면서, ${\frac{k-(a*x)}{y}}$가 0이 될 때 반복문을 종료하면, ${\frac{k-(a*x)}{y}}$ 값이 b가 된다.

이제 코드를 짜보자.

d, k = map(int, input().split())
# 피보나치 수 구하기
x = 1
y = 0
for i in range(d-1):
    x, y = y, x+y # y가 d번째 피보나치 수, x는 d-1번째 피보나치 수
for a in range(1, 100000): # a는 1부터 대입
    if (k-(x*a))%y == 0: # 나누어 떨어지면, 몫이 b가 됨.
        print(a, (k-(x*j))//y, sep="\n")
        break

x + y = 10이런 식으로 미지수 2개가 주어졌을 때마다 어떻게 풀어야 할지 몰라 당황했더랬다. 한 미지수(x)에 오름차순으로 값을 대입하면서 식이 성립되는 다른 미지수(y)를 찾는 식으로 푸는구나.

[문제 보기]

참조 : 백준 9625 - 피보나치 수열