[백준OJ] 14728번 벼락치기

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

14728번: 벼락치기

---

 

-풀이-

간단한 베낭문제이다. dp[i]=t 의 뜻은, i시간동안 최대 t의 점수를 얻을 수 있다는 뜻이다.

이것을 이용해서 먼저 시간기준 오름차순으로 정렬하고, 순서대로 탐색을 해가며, dp[i]와 dp[i-해당 단원의 시간]+해당단원을 공부했을때의 점수 를 비교해주어 더 큰 값을 갱신시켜주면된다.

 

-시간복잡도-

O(NT)

 

-코드-

#include <iostream>
#include<vector>
#include<algorithm>
#define TMAX 10001
using namespace std;

typedef pair<int, int> pii;
int N,T;
int dp[TMAX] = { 0 };
vector<pii> score;

void input() {
	cin >> N>>T;
	for (int i = 0; i < N; i++) {
		int K, S;
		cin >> K >> S;
		score.push_back({ K,S });
	}
}


void solution() {
	sort(score.begin(), score.end());
	for (int i = 0; i < score.size(); i++) {
		int k = score[i].first;
		int s = score[i].second;

		for (int i = T; i >= k;i--) {
			dp[i] = max(dp[i], dp[i - k] + s);
		}
	}
	cout << dp[T];
}

void solve() {
	input();
	solution();
}

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

	return 0;
}