[백준 17845번] 수강 과목 (C++)

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

17845번: 수강 과목

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, K, result;
int I[1001], T[1001], dp[1001][10001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> K;
    
    for(int i=1; i<=K; i++)
    {
        cin >> I[i] >> T[i]; //중요도, 공부시간
    }

    for(int i=1; i<=K; i++) //과목
    {
        for(int j=1; j<=N; j++) //최대 공부시간
        {
            if(j-T[i]>=0) dp[i][j] = max(dp[i-1][j], dp[i-1][j-T[i]] + I[i]); //배낭문제
            else dp[i][j] = dp[i-1][j];
        }
    }

    cout << dp[K][N];

    return 0;
}

 

기본적인 dp 배낭 알고리즘 문제이다.

주어진 공부시간 내에 최대 중요도를 담아주고 이를 출력한다.

 

참고 링크 : https://blob-thinking.tistory.com/297

[백준 1106번] 호텔 (C++)