[C++ 알고리즘] 백준 14728: 벼락치기

 

문제 설명

 

> 가장 기본적인 냅색문제, 평범한 배낭이랑 다른게 없음

 

 

 

 

해결 전략

 

>  보통 배낭문제는 2차원 배열을 만들거나, 배열 하나를 만들거나 둘 중 하나이다.

>  배열 하나를 만드는 것이 더 시간, 공간복잡도가 좋으므로 두 번째 방법으로 만들기

 

>  배낭문제를 접근하는 요소 중 가장 중요한게, 인덱스를 '배낭의 총 무게' 라고 생각하는 것이다.

>  1차원 배열을 활용하면 같은 인덱스가 들어가므로 for문을 내림차순으로 구현 

 

#include <iostream>

int dp[10001] = {};
int k[1001] = {};
int s[1001] = {};

int main() {
	std::ios::sync_with_stdio;
	std::cin.tie(0);

	int n, t;
	std::cin >> n >> t;

	for (int i{ 1 }; i <= n; i++) {
		std::cin >> k[i] >> s[i];
	}

	for (int i{ 1 }; i <= n; i++) {
		for (int j{ t }; j >= 1; j--) {
			if (j >= k[i]) dp[j] = std::max(dp[j], dp[j - k[i]] + s[i]);
		}
	}

	std::cout << dp[t] << "\n";
}