BOJ2502/ C++

https://www.acmicpc.net/problem/2502

2502번: 떡 먹는 호랑이

백준 온라인저지 2623번 문제입니다. 

DP을 이용해서 풀었습니다.

 

#include<iostream>
#define MAX 31
using namespace std;


int d, k;

int A[MAX];
int B[MAX];

void Input() {
	cin >> d >> k;
}

void solution() {
	A[1] = 1;
	A[2] = 0;
	B[1] = 0;
	B[2] = 1;
	for (int i = 3; i <= d; i++)
	{
		A[i] = A[i - 1] + A[i - 2];
		B[i] = B[i - 1] + B[i - 2];
	}

	for (int i = 1; i <= k; i++)
	{
		int Spare = k - (A[d] * i);
		if (Spare % B[d] == 0)
		{
			cout << i << endl << Spare / B[d] << endl;
			return;
		}
	}
}

int main(void) {
	Input();
	solution();
}

아이디어

피보나치 함수를 역으로 구하는 되는 문제임

할머니가 넘어온 날까지 필요한 첫번째 날과 두번째 날의 총 갯수를 구하여 첫쨋날과 두번째날에 준 떡의 갯수를 추적하는 방식으로 풀면됨