[백준/BOJ 알고리즘] 17845 수강 과목 C++

 

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

 

17845번: 수강 과목

 

0-1 Knapsack 문제이다.

링크 에서 0-1 Knapsack에 대해 알아볼 수 있다. (필자가 작성한 글임)

 

bottom-up 방식으로 DP를 구성하면 된다.

O(NK)의 시간복잡도를 갖는다.

#include <iostream>
#include <algorithm>
#define MAX_N 10001
#define MAX_K 1001
using namespace std;

int n,k;
int importance[MAX_N], studyTime[MAX_K], dp[MAX_K][MAX_N];

void solution() {
  for (int i=1; i<=k; i++) {
    for (int j=1; j<=n; j++) {
      if (studyTime[i] > j) dp[i][j] = dp[i-1][j];
      else dp[i][j] = max(dp[i-1][j], dp[i-1][j-studyTime[i]] + importance[i]);
    }
  }

  cout << dp[k][n] << "\n";
}

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  for(int i=1; i<=k; i++) { 
    cin >> importance[i] >> studyTime[i];
  }

  dp[0][0] = 0;
  solution();
}