백준 2502 : 떡 먹는 호랑이

www.acmicpc.net/problem/2502

2502번: 떡 먹는 호랑이

오늘 주는 떡 개수 = 전 날 준 떡 개수 + 전전날 준 떡 개수

보자마자 DP가 생각나는 문제이다. 다만 보통 dp랑 다른점은 초기 값을 모르고 중간 상태값을 가지고 초기 값을 추론해야 한다는 것이다.

 

첫 날에 주는 떡의 개수를 n개, 둘째 날에 주는 떡의 개수를 m개라고 하자. dp[1] = n, dp[2] = m, 그렇다면 dp[3] = n + m, dp[4] = m + n + m ... 이런 식으로 모든 날짜에 대해서 필요한 떡의 수를 n과 m의 방정식으로 표현할 수 있다.

dp방법을 사용하여 단순한 방정식 문제로 변환하고 나면 n과 m중 둘 중의 하나 값을 정해서 그 때의 n과 m이 해가 될 수 있는지 확인하면 된다. K의 최대 값은 100,000이고 날짜는 최대 30일이므로 아무리 연산 횟수가 많아도 300만번밖에 안걸린다. 그리고 사실 1<=A<=B 라는 조건이 있으므로 만약 A를 기준으로 해를 찾아 나간다면 1<=A<=K/2 인 구간에 대해서만 확인을 하면 될 것이다. A가 K/2를 넘어가는 경우는 절대 없다. A가 K/2인 경우는 dp[3]일 때 K인 경우에 만약 A와 B가 같다면 A = B = K/2가 된다. 코드로 구현하면 아래와 같다.

 

#include <iostream>

using namespace std;

pair<int, int> dp[31];

void DP(const int& d, const int& k) {
	int j;
	for (int i = 3; i <= d; i++) {
		dp[i].first = dp[i - 1].first + dp[i - 2].first;
		dp[i].second = dp[i - 1].second + dp[i - 2].second;
	}
	//이 때, i는 n의 계수(첫 째날 떡 개수의 계수), j는 m의 계수(둘 째날 ...)
	for (int i = 1; i <= k / 2; i++) {
		if ((k - dp[d].first * i) % dp[d].second == 0) {
			j = (k - dp[d].first * i) / dp[d].second;
			if (j >= i) {
				cout << i << '\n' << j; return;
			}
		}
	}
}

int main() {
	int d, k;
	cin >> d >> k;
	dp[1] = make_pair(1, 0);
	dp[2] = make_pair(0, 1);
	DP(d, k);
	return 0;
}

메모리: 2016 KB

시간: 0 ms