[백준2502] 떡 먹는 호랑이

문제출처: https://www.acmicpc.net/problem/2502

문제

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

예를 들어 첫째 날에 떡을 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)가 존재한다. 

풀이

수학을 잘하는사람이 코딩도 잘 한다는 것을 느낀 문제입니다. 문제의 조건을 수식에맞게 변수로 식을세워서 풀면 금방 답이 구해지는 문제인데, 아직 그런 학습이 부족해서인지 다른분들의 코드를 보고서야 이해를 했습니다.  이런 부류의 문제를 많이 풀어봐야겠습니다.

풀이는 스폐셜 저지, 즉 답이 여러개 일 수 있다는 점, 그래서 첫날(a)과 둘째날(b)을 1로잡고 하나씩 탐색해도되는점, 문제가 피보나치의 패턴이라는것만 알면 쉽습니다......

규칙을 보죠. 피보나치패턴에의해  첫날에 a, 둘째날에b만큼 주니, 다음과같이 식을 만들 수 있습니다.

a->b->a+b->a+2b->2a+3b..... 

a가 1,b=1부터 가정하므로(답이 여러개일 수 있으니 쉽게 a,b가 1개라고 가정하면서 탐색해본다는 마인드) k에 대한식을 세워보면 k=fibo[d-2]*a+fibo[d-1]*b입니다. 이 식을 세울줄 아는 능력(수학적 재능...)만있으면 끝입니다. 여기서 중요한건 a를 구하고 b를 구한다는 것, fibo[d-2],fibo[d-1]은 각각 a에대한 비율,b에대한 비율이라는것입니다. a는 1부터탐색해보고, 이때 가정한 a에 대해 b에대한 식b=(k-a*fibo[n-1])%fibo[n-2])을 세워서 b에대한 식이 나누어 떨어지면 (갯수는 정수이므로)a와 b가 구해진 겁니다. 끝입니다.

코드

#include<iostream>
using namespace std;
int fibo[31];
int main()
{
	int d, k;
	cin >> d >> k;
	fibo[1] = fibo[2] = 1;
	for (int i = 3; i <= d; i++)
	{
		fibo[i] = fibo[i - 2] + fibo[i - 1];
	}
	//a와 b의 계수(비율)
	int a_profit = fibo[d - 2];
	int b_profit = fibo[d - 1];
	//k=fibo(d-2)a+fibo(d-1)b;
	int a, b;
	for (int i = 1;; i++)
	{
		//a는 1부터 탐색해본다.
		a = i;
		//b에대한 식에대해 나누어떨어지면 답 구한거임)
		if ((k - a_profit * a) % b_profit)
			continue;
		//이 때 b는 구해진 a에대해 구함.
		b = (k - a_profit * a) / b_profit;
		break;
	}
	cout << a << endl << b << endl;
}

결과