백준 14728 c++ "벼락치기" -PlusUltraCode-

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

 

[필자 코드]

기본적인 배낭알고리즘 문제이다.

배낭 알고리즘의 본인만의 팁은 현재 값에서 특정값까지 하나하나 갱신해 간다는 느낌으로 하면 쉽게 문제를 해결할 수 있다.

다만 배낭문제에서 작은거에서 큰거로 접근하게 되면 중복되는 값이 발생할 수 있다.

그래서 끝에서 부터 접근해야 된다. 큰곳에서 작은곳으로

이 문제를 풀면서 알게 된 사실이다.

[코드 해설]

2. 입력 처리

먼저, N과 T를 입력받는다. 여기서 N은 선택할 수 있는 항목의 개수이며, T는 총 제한된 시간이다. 그런 다음, dp 벡터를 크기 T+1로 설정하여 각 시간에 대해 얻을 수 있는 최대 점수를 저장한다.

3. 동적 계획법을 이용한 최적해 탐색

각 항목에 대해 K(소요 시간)와 S(얻을 수 있는 점수)를 입력받는다.
이후, j = T부터 K 이상까지 역순으로 순회하며, dp[j] 값을 갱신한다.
즉, 현재 시간 j에서 K만큼 감소한 위치의 점수에 S를 더한 값과 기존 dp[j] 값 중 더 큰 값을 선택하는 방식으로 최적해를 찾는다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int N, T;
vector<int> dp;
int main(void) {
	cin >> N >> T;
	dp.resize(T+1);

	for (int i = 1; i <= N; i++) {
		int K, S;
		cin >> K >> S;
		for (int j = T; j >=K; j--) {
			dp[j] = max(dp[j], dp[j - K] + S);
		}
	}

	cout << *max_element(dp.begin(), dp.end());
}