[BOJ] 백준 14728 벼락치기 c++ (배낭, dp)

문제 출처 : https://www.acmicpc.net/problem/14728

14728번: 벼락치기

---

풀이

전형적인 배낭문제이다. 

입력 받은 pair 벡터를 순회하며 값마다 dp 배열을 업데이트 하면 된다.

 

여기서 for문을 뒤부터 돌린 이유는, 문제 조건에 한 단원에 한 문제를 출제한다. 라고 명시되어 있기 때문이다.

for문을 앞부터 돌리면 중복된 값이 계속해서 누적되기 때문에 뒤부터 돌린다.

 

최댓값을 구하므로, dp[j] 는 dp[j] 와 dp[j - 예상 공부 시간] + 해당 문제의 배점 의 최댓값으로 계산하면 된다.

vector<pair<int, int>> v(N+1); // time, score

for(int i = 1; i <= N; i++) {
    for(int j = T; j >= v[i].first; j--) {
        dp[j] = max(dp[j], dp[j - v[i].first] + v[i].second);
    }
}

---

코드

#include <bits/stdc++.h>

using namespace std;

int N, T;
int dp[10001];

int main(void) {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> N >> T;
	
	vector<pair<int, int>> v(N+1); // time, score

	for(int i = 1; i <= N; i++) {
		cin >> v[i].first >> v[i].second;
	}

	for(int i = 1; i <= N; i++) {
		for(int j = T; j >= v[i].first; j--) {
			dp[j] = max(dp[j], dp[j - v[i].first] + v[i].second);
		}
	}
	cout << dp[T] << '\n';

	return 0;
}