[백준] 12865번 평범한 배낭 C++ 코드

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n,k,w,v, a[100003][103];
vector<pair<int,int>> itm;

int go(int weight, int idx) {
  if(weight > k) return -987654321; // 무게 제한을 벗어나면 무효
  if(idx == n) return 0;  // 모든 물건을 확인한 경우 종료
  if(a[weight][idx] != -1) return a[weight][idx]; // 이미 계산된 값
  // 배낭을 선택하는 경우와 선택하지 않는 경우 비교
  int include = go(weight + itm[idx].first, idx + 1) + itm[idx].second;
  int exclude = go(weight, idx + 1);
  return a[weight][idx] = max(include, exclude);
}

int main() {
  cin >> n >> k;
  fill(&a[0][0], &a[0][0]+100003*103,-1); // 초기화
  for(int i = 0; i < n; i++) {
    cin >> w >> v;
    itm.push_back({w, v});
  }
  cout << go(0,0) << '\n';
  return 0;
}

풀이

냅색문제로 유명하다고 한다. 접근 방법은 간단하다. 가방에 물건을 넣는 경우와 넣지 않는 경우로 나눠지기 때문이다. 넣는 경우에는 무게를 증가시키고, 다음 인덱스로 넘어간다. 넣지 않는 경우에는 무게를 증가시키지 않고 다음 인덱스로 넘어간다. 

 

틀렸던 이유

1. idx가 n-1일 때 물건의 가치를 반환하게 했는데, 이렇게 되면 n - 1에 접근하자마자 바로 종료해서 마지막 값이 무조건 들어가게 됐다. 이 문제를 통해 idx == n 일 때 return 0;를 사용하면 된다는 것을 배웠다.
2. weight로 1차원 배열만 만들어서 했던 게 문제가 됐다. 이로 인해 다른 상태이지만 동일한 weight값을 가지는 경우 덮어쓰게 되어 잘못된 결과를 초래할 수 있다.