[백준] 17845 수강 과목

문제 링크

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

사용 알고리즘

• DP

풀이

자주 접할 수 있는 DP 문제이다.

 

공부 시간에 따른 최대 중요도를 저장하는 DP 배열을 만든 뒤,

각 과목별로 `max(현재 최대 중요도, 현재 공부 시간 - 해당 과목의 필요한 공부 시간 + 해당 과목을 공부했을 때 얻을 수 있는 중요도)`를 구하면 된다.

 

이 때 과목별로 현재 시간에 따른 중요도를 갱신하는 과정에서 `t ~ n + 1`로 반복하면 동일한 중요도가 더해질 수 있기 때문에 뒤에서부터(`n ~ t - 1`) 반복하는 것으로 해결할 수 있다.

코드

import sys, os, io, atexit

input = lambda: sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode("ascii"))
atexit.register(lambda: os.write(1, stdout.getvalue()))

n, k = map(int, input().split())
sub = sorted(tuple(map(int, input().split())) for _ in range(k))

dp = [0] * (n + 1)
for i, t in sub:
    for j in range(n, t - 1, -1):
        dp[j] = max(dp[j], dp[j - t] + i)
print(dp[-1])