[백준(BOJ)] 12865번 : 평범한 배낭 - C++[CPP]

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

12865번: 평범한 배낭

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 다이나믹 프로그래밍
• 배낭 문제

 

---

 

⊙ 문제 접근 과정

 

처음 접근할 땐, vector 두 개를 사용하고 sort에 또 다른 함수를 만들어서 정렬해주는 바람에 코드 길이가 길었지만 더 효율적으로 문제를 푸는 방법이 있었다. 아래에서 소개하겠다.

 

max함수를 이용하면 문제를 쉽게 풀 수 있다.

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <vector>

using namespace std;

int N,K;
vector<pair<int,int>> backpack;
int arr[100001];


int main() {
    cin >> N >> K;
    
    for(int i=0;i<N;i++) {
        int v,w;
        cin >> v >> w;
        backpack.push_back({v,w});
    }
        
    for (int i = 0; i < N; i++) {
        for (int j = K; j >= 1; j--) {
            if (backpack[i].first <= j) {
                arr[j] = max(arr[j], arr[j - backpack[i].first] + backpack[i].second);
            }
        }
    }

    cout << arr[K];
    
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!