백준 17845번 : 수강 과목 (C 언어)

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

17845번: 수강 과목

Code:

#include <stdio.h>
#define max(a,b) (a>b)?a:b
 
int n, k;
int l[10001] = { 0, };
int t[10001] = { 0, };
int dp[1001][10001] = { 0, };
 
int main()
{
    scanf("%d %dx", &n, &k);
    for (int i = 1; i <= k; i++)
    {
        scanf("%d %d", &l[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]] + l[i]);
            }
            else
            {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    printf("%d", dp[k][n]);
}

문제 설명

유니스트 컴퓨터공학과에 다니는 서윤이는 다음 학기 어떤 과목을 들을지 고민 중입니다. 서윤이는 학점을 잘 받기 위해 노력하고자 하며, 동시에 과목의 중요도를 고려하여 과목을 선택하려고 합니다. 그런데, 서윤이는 자신의 공부 시간에는 한계가 있기 때문에, 최대 중요도를 얻으면서도 공부 시간 제한 내에서 몇 개의 과목을 선택해야 하는지 알고 싶습니다.

주어진 입력으로부터, 서윤이가 최대 중요도를 얻을 수 있도록 과목을 선택하는 프로그램을 작성해 보겠습니다.

입력

• 첫 줄에는 서윤이의 최대 공부시간 N과 과목 수 K가 주어집니다. (1 ≤ N ≤ 10,000, 1 ≤ K ≤ 1,000)
• 이후 K개의 줄에는 각 과목의 중요도 I와 필요한 공부시간 T가 주어집니다. (1 ≤ I ≤ 100,000, 1 ≤ T ≤ 10,000)

출력

• 얻을 수 있는 최대 중요도를 출력합니다.

코드 설명

 

1. 먼저 최대 공부시간 N과 과목 수 K를 입력으로 받습니다.
2. 각 과목의 중요도와 필요한 공부시간을 배열에 저장합니다.
3. 중첩 반복문을 통해 모든 과목과 가능한 공부 시간에 대해 최대 중요도를 계산합니다.
4. dp[i][j] 배열을 활용하여 이전 과목까지 고려한 상태에서 현재 과목을 선택하거나 선택하지 않는 경우 중 중요도가 높은 것을 선택합니다.
5. 최종 결과는 dp[k][n]에 저장된 최대 중요도를 출력합니다.