[Python] 17845번 수강 과목

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

17845번: 수강 과목

---

 

22/10/04

 

 

전형적인 배낭 문제이다.

---

 

문제 접근 방식:

 

 

이 문제에서는 서윤이가 공부에 투자할 수 있는 시간의 한계가 존재하므로, 서윤이가 쓸 수 있는 총 공부 시간의 한계, 다시 말해 이 문제에서는 N의 값을 배낭의 한계허용치라고 생각할 수 있다.

 

과목의 중요도의 합이 최대가 되도록 시간을 써야 하므로, 각 과목의 중요도는 배낭에 담는 물건의 가치라고 생각할 수 있다.

 

이를 고려하자면 다음과 같다.

 

DP[i][j] = i번째 과목까지 주어져 있는 상태고, j시간을 공부에 할애할 수 있을 때 중요도의 합의 최댓값

 

우리의 목적은 DP[K][N]의 값을 구하는 것이 우리의 목적이다.

 

만약 i번째 과목에 도저히 시간을 쓸 수 없는 상황이라면, 다시 말해, time[i] > j라면, DP[i][j] = DP[i-1][j]이다.

 

그렇지 않다면, DP[i][j] = max(DP[i][j-time[i]] + value[i], DP[i-1][j])가 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 17845번 수강 과목
# DP, 배낭 문제
'''
접근 방법:
DP[i][j] = i번째 과목까지 있고, j시간을 공부에 할애할 수 있을 때 중요도의 합의 최댓값
DP[K][N]을 구하는 것이 우리의 목적

if time[i] > j:
DP[i][j] = DP[i-1][j]
else:
DP[i][j] = max(DP[i][j - time[i]] + value[i], DP[i-1][j])
'''
import sys
input = sys.stdin.readline

N, K = map(int, input().rstrip().split())
DP = [[0 for _ in range(N+1)] for _ in range(K+1)]
value = [0]
time = [0]
for _ in range(K):
    v, t = map(int, input().rstrip().split())
    value.append(v)
    time.append(t)

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

print(DP[K][N])