백준 - 평범한 배낭) 복습을 위해 작성하는 글 2024-01-02

📘 백준 - 평범한 배낭

문제 링크 : https://www.acmicpc.net/problem/12865

📝 구현

// C++
//#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
	cin.tie(NULL); ios::sync_with_stdio(false);
	int n, k;
	cin >> n >> k;

	int weight, value;
	vector<int> table(k + 1); // k번째 인덱스도 접근해야하기 때문에 k + 1

	for (int i = 0; i < n; ++i) {
		cin >> weight >> value;
        
        // 입력받은 weight가 무게 제한보다 크면 불필요한 데이터이기 때문에 무시
		if (weight > k) continue;
        
        // 상향식 검사 시, 큰 인덱스에 접근하는 일이 생기기 때문에 하향식 검사
		for (int j = k; j > 0; --j) {
        // 기존에 value 값이 존재하면서 기존의 weight와 현재 weight의 합이 무게 제한보다 작거나 같을 때
			if (table[j] != 0 && j + weight <= k)
            // value가 더 큰 값으로 수정
				table[j + weight] = table[j + weight] > table[j] + value ? table[j + weight] : table[j] + value;
		}
        // 현재 value값에 현재 value값을 비교하여 더 큰 값으로 수정
		table[weight] = table[weight] > value ? table[weight] : value;
	}
	cout << *max_element(table.begin(), table.end());

	return 0;
}

👨‍💻 구현 설명

• k + 1만큼의 크기로 weight(index)에 맞게 value를 저장할 테이블을 만든다. (k번째 인덱스도 필요하므로 k+1)
• 입력된 무게가 k(무게 제한)보다 크다면 무시한다.
• j(인덱스)와 weight를 더했을 때 k보다 크고 table[j]가 0이 아닐 때 검사한다.
  - 이유는 기존에 물건이 있는지와 물건이 있더라도 그 물건과의 weight의 합이 k를 넘으면 의미가 없기 때문이다.
• 또한 기존에 있던 무게에 같은 무게의 물건이 들어온다면 더 높은 value의 값으로 수정한다.
• 이 과정을 통해 table의 최대 요소가 정답이 될 것이다.
• 시간 복잡도는 O(n * k)이다.
  
  

🙄 Thinking...

• 처음 문제를 봤을 땐 완전 탐색 문제인가 싶었지만, n의 최대 제한이 100 이하이기 때문에
  완전 탐색으로 문제를 푼다면 O(2^100 - 1)이라는 시간 복잡도가 예상되었다.
• 2차원 테이블을 그려보고, 경우의 수를 써 내려가며 생각해 보다가, 반복되는 작은 문제들이 있었고, 그 문제들의 Optimal Solution을 이용하여 다음 해를 손쉽게 구할 수 있다는 것을 알 수 있었다.
• 때문에 DP(다이나믹 프로그래밍) 기법을 사용하여 문제를 해결하였다.