17845번: 수강 과목
첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다. 이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이
www.acmicpc.net
문제
유니스트 컴퓨터공학과에 다니는 서윤이는 이번에 어떤 과목을 들을지 고민중이다. 학점을 잘 받을 수 있으면서도 중요한 과목을 듣고 싶은 서윤이는 모든 과목의 중요도와, 일정 이상의 학점을 받기 위해 필요한 공부시간을 다 적었다.
처음에는 모든 과목을 들으려고 했던 서윤이는 자신의 공부 시간에 한계가 있다는 것을 깨달았다. 그래서, 공부 시간의 한계를 초과하지 않으면서 과목의 중요도 합이 최대가 되도록 몇 개만 선택하여 수강하기로 마음먹었다.
중요도가 최대가 되도록 과목을 선택했을 때, 최대가 되는 중요도를 출력하는 프로그램을 작성하시오.
입력
첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다.
이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이 공백을 사이에 두고 주어진다.
출력
얻을 수 있는 최대 중요도를 출력한다.
코드
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
info = [[]]
for _ in range(k):
l, t = map(int, input().split())
info.append([l, t])
dp = [[0] * (n+1) for _ in range(k+1)] # 최대 중요도
for i in range(1, k+1):
for j in range(n+1):
if j < info[i][1]: # 시간이 현재 과목에 필요한 공부시간보다 작은 경우
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j-info[i][1]]+info[i][0], dp[i-1][j])
print(dp[k][n])
가치의 합이 최대가 되도록 물건을 담는 0-1 배낭문제이다. 0-1 배낭문제는 DP를 이용하여 풀이할 수 있다.
dp 배열에는 i번째 물건을 담거나/안 담았을 때 j 시간을 공부하고 최대가 되는 중요도의 합을 저장한다. 만약 쓰려는 공부시간보다 i번째 과목에 필요한 시간이 더 크다면 i번째 과목을 수강하지 않는다. 따라서 dp[i][j]에는 dp[i-1][j]의 중요도 값이 저장되게 된다. 그게 아니라면 i번째 과목을 수강할지 안 할지 선택해야 한다. 우리는 최대 중요도가 나오도록 하기 위해 두 경우 중 큰 값을 골라주도록 한다.
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 1699번 제곱수의 합 (0) | 2023.11.05 |
---|---|
[Python/파이썬] 백준 1965번 상자넣기 (0) | 2023.10.28 |
[Python/파이썬] 백준 3067번 Coins (0) | 2023.10.13 |
[Python/파이썬] 백준 2629번 양팔저울 (0) | 2023.10.10 |
[Python/파이썬] 백준 20542번 받아쓰기 (0) | 2023.09.26 |