[BOJ] 2502번_떡 먹는 호랑이_DP (C++)

[문제]

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

하루에 한 번 산을 넘어가는 떡 장사 할머니는 호랑이에게 떡을 주어야 산을 넘어갈 수 있는데, 욕심 많은 호랑이는 어제 받은 떡의 개수와 그저께 받은 떡의 개수를 더한 만큼의 떡을 받아야만 할머니를 무사히 보내준다.

예를 들어 첫째 날에 떡을 1개 주었고, 둘째 날에 떡을 2개 주었다면 셋째 날에는 3개 넷째 날에는 5개, 다섯째 날에는 8개, 여섯째 날에는 13개를 주어야만 무사히 산을 넘어갈 수 있다.

우리는 산을 무사히 넘어온 할머니에게 오늘 호랑이에게 몇 개의 떡을 주었는지, 그리고 오늘이 호랑이를 만나 떡을 준지 며칠이 되었는지를 알아내었다. 할머니가 호랑이를 만나서 무사히 넘어온 D째 날에 준 떡의 개수가 K개임을 알 때, 여러분은 할머니가 호랑이를 처음 만난 날에 준 떡의 개수 A, 그리고 그 다음 날에 호랑이에게 준 떡의 개수 B를 계산하는 프로그램을 작성하시오. 이 문제에서는 항상 1 <= A <= B 이다.

예를 들어 여섯 번째 날에 산을 무사히 넘어온 할머니가 호랑이에게 준 떡이 모두 41개라면, 호랑이를 만난 첫 날에 준 떡의 수는 2개, 둘째 날에 준 떡의 수는 7개이다. 즉 셋째 날에는 9개, 넷째 날에는 16개, 다섯째 날에는 25개, 여섯째 날에는 41개이다. 따라서 A=2, B=7이 된다. 단 어떤 경우에는 답이 되는 A, B가 하나 이상일 때도 있는데 이 경우에는 그 중 하나만 구해서 출력하면 된다.

[사용 알고리즘]

DP(다이나믹 프로그래밍)

[풀이 핵심]

• 이 문제는 피보나치 수에 대해 알고 있으면 쉽게 해결할 수 있다. 피보나치 수란, 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두항의 합인 수열이다. 1,1,2,3,5,8,13,21 이런식으로 진행 되는 수열을 피보나치 수라고 한다.
• dp_a[] 배열에는 해당 날의 a개수, dp_b[] 배열에는 해당 날의 b개수를 저장한다. 쉽게 설명하면 첫째날 = a, 둘째날 = b, 셋째날 = a+b, 넷째날 = b+(a+b) = a+2b, 다섯째날 = (a+b)+(b+(a+b)) = 2a+3b. 이런식으로 할머니가 산을 넘어온 날인 D까지 dp_a[], dp_b[]에 값을 넣어준다.
• 마지막으로 2중 for문으로 a와 b에 값을 넣어가며 맞는 날을 찾으면 된다. dp_a[D] i + dp_b[D] j == K는 할머니가 산을 넘어온 날의 떡 개수를 뜻하는데, 여기서 dp_a[D]와 dp_b[D]는 계수이므로 i와 j는 a,b가 된다. 즉 i,j가 첫째날과 둘째날에 준 떡의 개수가 된다.

[코드]

//boj2502번_떡 먹는 호랑이_dp

#include<iostream>

using namespace std;

int dp_a[31];
int dp_b[31];

int main() {
	int D, K;
	cin >> D >> K;

	dp_a[1] = 1;
	dp_a[2] = 0;
	dp_a[3] = 1;

	dp_b[1] = 0;
	dp_b[2] = 1;
	dp_b[3] = 1;

	for (int i = 3; i <= D; i++) {
		dp_a[i] = dp_a[i - 2] + dp_a[i - 1];
		dp_b[i] = dp_b[i - 2] + dp_b[i - 1];
	}

	for (int i = 1; i < 100000; i++) {
		for (int j = 1; j < 100000; j++) {
			if (dp_a[D] * i + dp_b[D] * j == K) {
				cout << i << '\n';
				cout << j;

				return 0;
			}
		}
	}
}