[백준 17845] 수강 과목

문제 링크

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

 

문제 요약

최대 공부시간 \(N\)과 과목 수 \(K\)가 주어진다. 이어서 각 과목 \(i\)의 중요도 \(I_i\)와 필요한 공부시간 \(T_i\)가 주어진다. 최대 공부시간 \(N\)을 초과하지 않으면서 중요도 합이 최대가 되도록 과목을 선택할 때, 최대 중요도를 구하는 문제이다.

 

문제 풀이

이 문제는 전형적인 배낭 문제(Knapsack Problem)로 동적 계획법(Dynamic Programming)을 이용해 풀 수 있다. 동적 계획법은 Top Down 방식과 Bottom Up 방식으로 풀 수 있는데, 여기서 두 가지 방법 모두를 이용해 문제를 푸는 방법을 소개한다.

 

Top Down 방식으로 문제 풀기

동적 계획법을 Top Down 방식으로 풀 때는 보통 재귀적인 방법을 사용한다. i번째 과목까지 고려했을 때, 남은 공부 시간 left를 이용해서 얻을 수 있는 최대 중요도를 얻을 수 있는 함수 func(idx, left)이 있다고 생각해 보자. 그렇다면 func(idx, left)는 아래와 같은 정의를 할 수 있다.

func(idx, left)의 점화식

만약 남은 공부 시간이 현재 과목의 공부 시간보다 크거나 같다면 현재 과목을 선택하는 것을 고려해 볼 수 있다. 하지만 남은 공부 시간이 현재 과목의 공부 시간보다 작다면 현재 과목은 선택하면 안 된다. 이 점화식을 메모이제이션 기법을 이용해 구현하면 다음과 같다.

int func(int idx, int left) {
    if (idx == -1) {
        return 0;
    }
    
    int& ret = dp[idx][left];
    
    if (ret != -1) {
        return ret;
    }
    
    ret = func(idx - 1, left);
    
    if (left >= T[idx]) {
        ret = max(ret, func(idx - 1, left - T[idx]) + I[idx]);
    }
    
    return ret;
}

 

Bottom Up 방식으로 문제 풀기

공부 시간 k를 사용하여 얻을 수 있는 최대 중요도를 나타내는 DP 테이블 dp[k]가 있다고 생각해 보자. 각 과목에 대해, 현재 과목을 포함하는 경우와 포함하지 않는 경우를 고려하여 DP 테이블을 업데이트할 수 있다. 업데이트를 할 때는 N부터 \(T_i\)까지 역순으로 업데이트를 해줘야 한다는 것을 유의해야 한다. 만약 \(T_i\)부터 N까지 순차적으로 업데이트를 해준다면 해당 과목을 여러 번 선택할 수 있기 때문이다. 이를 코드로 구현한다면 다음과 같다.

int solve() {
    memset(dp, -1, sizeof(dp));
    
    dp[0] = 0;
    
    for (int i = 0 ; i < k ; ++i) {
        for (int j = n ; j >= T[i] ; --j) {
            if (dp[j - T[i]] != -1) {
                dp[j] = max(dp[j], dp[j - T[i]] + I[i]);
            }
        }
    }
    
    int ans = 0;
    
    for (int i = 0 ; i <= n ; ++i) {
        ans = max(ans, dp[i]);
    }
    
    return ans;
}

Bottom Up 방식은 기저사례부터 차근차근 쌓아나가기 때문에 메모리 사용량을 절약할 수 있는 장점이 있지만 Top Down 방식이 가지는 직관적인 구현이란 장점도 있으니 상황에 맞게 잘 선택하면 될 것 같다.