Algorithm/📊 Problem Solving

[백준/BOJ] 17845 - 수강 과목

posted by sangmin

17845 - 수강 과목

문제

유니스트 컴퓨터공학과에 다니는 서윤이는 이번에 어떤 과목을 들을지 고민중이다. 학점을 잘 받을 수 있으면서도 중요한 과목을 듣고 싶은 서윤이는 모든 과목의 중요도와, 일정 이상의 학점을 받기 위해 필요한 공부시간을 다 적었다.

처음에는 모든 과목을 들으려고 했던 서윤이는 자신의 공부 시간에 한계가 있다는 것을 깨달았다. 그래서, 공부 시간의 한계를 초과하지 않으면서 과목의 중요도 합이 최대가 되도록 몇 개만 선택하여 수강하기로 마음먹었다.

중요도가 최대가 되도록 과목을 선택했을 때, 최대가 되는 중요도를 출력하는 프로그램을 작성하시오.

코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())

importance, time = [], []
for _ in range(K):
    I, T = map(int, input().split())
    importance.append(I)
    time.append(T)

dp = [[0 for _ in range(N+1)] for _ in range(K+1)]

for i in range(1, K+1):
    for j in range(1, N+1):
        if j >= time[i-1]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-time[i-1]] + importance[i-1])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[K][N])

한마디

과목을 선택한다, 선택하지 않는다 두 가지 경우밖에 없으므로 0-1 배낭정리 유형이다.

 

17845번: 수강 과목

첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다.  이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이

www.acmicpc.net