BOJ - 2502번 떡 먹는 호랑이(C++)

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

문제 난이도

Silver 1

문제 접근법

피보나치 수열의 거꾸로라고 생각하면 쉽다.
D일 째 있는 수가 K 라면, D-1일 때 K보다 작은 수로 들어갈 수 있다.
그럼 D-1일 때 수를 변하는 수 : a라고 생각해보면 D-2 일 때 수는 : 41-a가 된다.
이런 원리를 사용해서 dfs와 완탐으로 문제를 해결했다.

통과 코드

#include <iostream>
#include <algorithm>

using namespace std;

int D, K;
int A=-1, B=-1;

void dfs(int a, int b, int cnt) {
	if (a <= 0 || b<=0) return;
	if (cnt == 2) {
		A = a;
		B = a + b;
		return;
	}
	dfs(b, a - b, cnt-1);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> D >> K;
	for (int i = K - 1; i >= 1; i--) {
		dfs(i, K - i, D);
		if (A != -1 && B != -1) break;
	}
	cout << A << "\n";
	cout << B << "\n";
	return 0;
}