백준[14728] 벼락치기

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

14728번: 벼락치기

.

준석이는 주어진 시간 안에 최대한의 점수를 주는 과목들을 공부해야한다.

각 과목은 cost와 그에대한 가치  value가 있다.

주어진 cost 안에 과목들의 가치의 총 합이 최대가 되게하는 과목집합을 구해야한다.

 

이 문제를 어떻게 풀어야할까?

 

쉬운 방법으로는 모든 경우의 수를 구할 수 있다. 하지만 단순 계산해보아도 경우의 수가 2^100이나 된다. 제한시간 안에는 이런 방법으로는 풀 수 없다.

 

그렇다면 분할정복으로 풀 수있을까?

문제를 조금 단순하게 말해서 "효율"이라는 단어를 사용하겠다.

 

어떤 과목집합 S와 S의 원소 a가 있다.

주어진 T안에 S를 효율적으로 공부했을때 최대 점수 =

max(S에서 a를 포함해서 공부했을때 최대 점수, S에서 a를 제외하고 공부했을때 최대 점수)

이렇게 분할정복 식을 만들어봤다. 조금더 정리해보자

solve( S, T ) = max( solve( S-a, T-at) + value[a], solve( S-a, T ) )

대충 이런식이다. 이 식은 두개의 매개변수에 대해서 항상 같은 값을 반환하는 함수이기때문에 memozation을 적용할 수 있다.

따라서 이 문제는 분할 정복에서 DP가 되었다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#define FOR(i, n) for(int i = 0; i < n; i++)

using namespace std;

int N, T;

int arr[101][2];
int cache[101][10001];

int solve(int index, int t) {
	if (index == N - 1) {
		if (arr[index][0] <= t) {
			return arr[index][1];
		}
		else {
			return 0;
		}
	}

	if (cache[index][t] > -1) return cache[index][t];

	int a = arr[index][0];
	int ret;
	if (arr[index][0] <= t) {
		ret = solve(index + 1, t - a) + arr[index][1];
	}
	else ret = 0;
	cache[index][t] = max(ret, solve(index + 1, t));
	return cache[index][t];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	FOR(i, 101) FOR(j, 10001) cache[i][j] = -1;
	cin >> N >> T;

	for (int i = 0; i < N; i++) {
		cin >> arr[i][0] >> arr[i][1];
	}
	int ans = solve(0, T);
	cout << ans;
	return 0;
}