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

2502번: 떡 먹는 호랑이

완전 탐색을 이용한 문제이다. 첫날 떡 갯수를 a, 둘째날 떡 갯수를 b라고 했을때, 아래와 같은 방식으로 갯수가 늘어남을 알 수 있다.

• 첫째날 - 1a + 0b
• 둘째날 - 0a + 1b
• 셋째날 - 1a + 1b
• 넷째날 - 1a + 2b
• 다섯째날 - 2a + 3b
• 여섯째날 - 3a + 5b
• n번째날 - n-1번째날 + n-2번째날

반복문을 통해 주어진 D번쨰 날에 해당하는 a와 b의 배수를 구해준 뒤, a를 기준으로 b를 구하는 반복문을 돌려준다. 만약 여섯째날이라면 5b = K - 3a -> b = (K - 3a) / 5로 나타낼 수 있다. (K - 3a) % 5 == 0일 경우를 찾아 출력해주었다.
간단하게 풀 수 있었다. dp 문제인데 dp를 이용하지 않고 반복문으로 해결한 점이 좀 걸리긴 했다.

#include <iostream>

using namespace std;

int D, K;

void solution() {
	int a = 1, b = 1;
	int pre_a = 0, pre_b = 1;

	for (int i = 4; i <= D; i++) {
		int tmp_a = a;
		int tmp_b = b;

		a += pre_a;
		b += pre_b;

		pre_a = tmp_a;
		pre_b = tmp_b;
	}

	int result_a = 0, result_b = 0;
	for (int i = 1; i <= K / 2; i++) {
		result_a = a * i;
		if ((K - result_a) % b == 0) {
			result_b = (K - result_a) / b;
			result_a = i;
			break;
		}
	}

	cout << result_a << "\n" << result_b;
}

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

	cin >> D >> K;

	solution();
	
	return 0;
}