[백준 #2502] 떡 먹는 호랑이 (C++)

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

2502번: 떡 먹는 호랑이

 

첫날의 준 떡의 개수는 A, 둘째 날에 준 떡의 개수는 B이므로

셋째 날에는 A+B, 넷째 날에는 A+2B 식으로 늘어난다.

 

A와 B의 계수를 담을 배열을 각각 만든 후

a[1] = 1, a[2] = 0

b[1] = 0, b[2] = 1 값을 미리 준다.

 

그다음부터는 피보나치의 수열처럼 계산하면 되므로

for 문을 사용해 값을 얻을 수 있다.

 

그다음 새로운 for 문을 통해

첫째 날 주는 떡의 개수를 1부터 k까지 늘려가면서

이를 계산하고 남은 떡의 양과 B의 계수가 나누어떨어진다면

첫째 날 주는 떡의 개수와 둘째 날 주는 떡의 개수를 출력하였다.

 

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int d, k;
	int a[31], b[31];

	cin >> d >> k;

	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 tmp = k - (a[d] * i);
		if (tmp % b[d] == 0) {
			cout << i << "\n" << tmp / b[d];
			break;
		}
	}
	return 0;
	
}