문제

SW 역량 테스트는 총 T분동안 진행되며 N개의 문제가 나온다. 대회가 진행되는 동안 아무 때나 소스 코드를 제출할 수 있다.

i번 문제를 t분에 맞춘 경우에는 Mi-t*Pi 점을 받게 된다. 이 테스트에 응시한 백준이가 i번 문제를 푸는데 걸리는 시간은 Ri분이다.

백준이가 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성하시오.

문제풀이

사용한 알고리즘 : Greedy, DP

강산님의 글을 참고하여 풀이를 작성하였습니다.

생각해보면, P_i 는 페널티 느낌으로, P_i 가 클 수록 늦게 풀면 완전 손해입니다.

더 나아가 문제풀이가 t 시간 진행 된 후, a, b 두 문제를 풀어 얻는 점수를 생각해보면

1] a 풀고 b 푸는 경우 얻는 점수 :

M_a-(t+R_a)*P_a + M_b-(t+R_a+R_b)*P_b

2] b 풀고 a 푸는 경우 얻는 점수 :

M_b-(t+R_b)*P_b + M_a-(t+R_b+R_a)*P_a

입니다.

a 먼저 푸는게 이득이려면 1] - 2] > 0 이어야 겠죠?

1] - 2] = R_b*P_a - R_a*P_b > 0 이면 a 먼저 푸는게 이득입니다.

즉 R_a/P_a < R_b/R_a 이면 a 먼저 푸는게 이득입니다.

따라서 Greedy 느낌으로 R/P 가 작은거부터 푸는게 이득일겁니다.

과정(1) 의 생각을 구현하는 struct 를 만들고, 이를 sort 해줍니다. (R/P가 작은게 먼저오게)

sort 된 문제들을 차례로 탐색하며 dp 로 푸는 함수를 만듭니다.

'dp[k][t] : k번째 문제, t의 시간 에서 얻을 수 있는 최대 점수' 라고 설정하였습니다.

각 문제를 탐색 할 때

1] 안 풀고 넘기는 경우

2] 풀고 넘기는 경우

2가지 경우가 있겠죠?

안 풀고 넘기면 시간을 안쓰고, 풀고 넘길 경우 시간을 쓰고 점수를 얻겠죠...

문제를 풀 경우는 현재시간 + 문제풀이시간 <= 제한시간 이어야 합니다.

	#include <bits/stdc++.h>
	using namespace std;
	typedef long long ll;

	int N;
	ll T;
	struct Node {
	ll M;
	ll P;
	ll R;
	Node() {
	M = 0LL;
	P = 0LL;
	R = 0LL;
	}
	bool operator < (const Node& rhs) const {
	return R * rhs.P < rhs.R* P; // R/P 가 작은거 우선
	}
	};
	Node arr[111111];

	ll dp[55][111111];
	ll path(int idx, ll time) {
	if (idx == N) return 0LL; // 다봄

	ll& ret = dp[idx][(int)time];
	if (ret != -1) return ret;

	ret = path(idx + 1, time); // 이번꺼 안해봄
	if (time + arr[idx].R <= T) // 이번꺼 해보기
	ret = max(ret, arr[idx].M - (time + arr[idx].R) * arr[idx].P + path(idx + 1, time + arr[idx].R));

	return ret;
	}

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

	cin >> N >> T;

	for (int i = 0; i < N; ++i) cin >> arr[i].M;
	for (int i = 0; i < N; ++i) cin >> arr[i].P;
	for (int i = 0; i < N; ++i) cin >> arr[i].R;

	sort(arr, arr + N);
	memset(dp, -1, sizeof(dp));
	cout << path(0, 0LL) << '\n';

	return 0;
	}

view raw BOJ 13448.cpp hosted with ❤ by GitHub