백준 2502번 떡 먹는 호랑이 C++

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

조금 특이한? dp 문제이다.

우선 점화식을 세울 때 생각한 것은 어떤 날이든 첫째 날과 둘째 날의 떡의 개수로 분해할 수 있다는 것이다.

예를 들어 5번째 날은 3번째 날 + 4번째 날이고, 3번째 날은 1번째 날 + 2번째 날, 4번째 날은 2번째 날 + 3번째 날.. 이런 식으로 밑으로 내려가면서 최종적으론 1번째 날과 2번째 날의 떡의 개수의 조합으로 나타낼 수 있다.

그림으로 나타내면 이런 식으로, 5번째 날은 최종적으로 2 * 1번째 날, 3* 2번째 날의 떡의 개수로 나타낼 수 있다.

 

하지만 숫자가 주어질 때마다 이런 식으로 계속 분해하면 시간이 오래 걸리기 때문에 bottom-up 방식으로 해결하기로 생각했다.

pair을 이용하여 dp배열을 만들었는데, 첫 번째 원소는 첫 번째 날 떡의 개수의 수량이고, 두 번째 원소는 두 번째 날 떡의 개수의 수량이다.

dp[1]은 첫 번째 날이므로 첫 번째 날 떡의 개수를 1개만 가지고 있기 때문에 {1, 0}이고,

dp[2]는 두 번째 날이므로 두 번째 날 떡의 개수를 1개만 가지고 있기 때문에 {0 , 1} 이다.

dp[3]부터는 dp[3-2] + dp[3-1] 이기 때문에 {dp[3-2].first + dp[3-1].first , dp[3-2].second+dp[3-1].second} 로 구할 수 있다.

이것을 이용하여 만든 점화식은 dp[i] = { dp[i - 2].first + dp[i - 1].first, dp[i - 2].second + dp[i - 1].second } 이다.

이 식을 이용해서 dp[5]를 구하면 {2, 3}이 나온다. 위의 그림과 같은 결과가 나오는 것을 볼 수 있다.

 

이제 k를 이용하여 첫 번째 날의 떡의 개수와 두 번째 날 떡의 개수를 구해야 한다.

첫 번째 예제에서는 6일째에 41개를 줬다고 했다. dp[6]은 {3, 5} 이다.

첫째 날에 한 개를 줬다고 가정하면, 3 * 1 + 5 * 두 번째 날 떡의 개수 = 41 이 되어야 하는데, 두 번째 날 떡의 개수가 자연수가 나오지 않기 때문에 답이 될 수 없다.

첫째 날에 두 개를 줬다고 가정하면, 3 * 2 + 5 * 두 번째 날 떡의 개수 = 41이고, 여기서는 두 번째 날 떡의 개수가 7이 되기 때문에 답이 될 수 있다.

답은 여러 개가 될 수 있는데, 그중 아무거나 출력해도 된다고 하니 제일 먼저 나온 답을 출력하면 된다.

그러므로 첫 번째 예제의 정답은 첫째 날에는 2개, 둘째 날에는 7개를 준 경우이다.

 

두 번째 예제의 결과는 2, 26이 나왔는데 계산해보면 2, 26, 28, 54, 82, 136, 218이 되고, 정답 처리되었다.

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <unordered_set>

using namespace std;
typedef long long ll;

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

	int d, k;
	cin >> d >> k;
	vector<pair<int, int>> dp(d + 1, { 0,0 });
	dp[1] = { 1,0 };
	dp[2] = { 0,1 };
	for (int i = 3; i <= d; i++) {
		dp[i] = { dp[i - 2].first + dp[i - 1].first,dp[i - 2].second + dp[i - 1].second };
	}
	int first = dp[d].first;
	int second = dp[d].second;
	int ans1 = 1;
	while ((k - (first * ans1)) % second != 0) {
		ans1++;
	}
	int ans2 = (k - (first * ans1)) / second;
	cout << ans1 << "\n" << ans2;
};