[백준 17845번] 파이썬 - 수강 과목

백준 17845 - 수강 과목

시간 제한 1초, 메모리 제한 512MB

# 조건

• 유니스트 컴퓨터공학과에 다니는 서윤이는 이번에 어떤 과목을 들을지 고민중이다.
• 학점을 잘 받을 수 있으면서도 중요한 과목을 듣고 싶은 서윤이는 모든 과목의 중요도와, 일정 이상의 학점을 받기 위해 필요한 공부시간을 다 적었다.
• 처음에는 모든 과목을 들으려고 했던 서윤이는 자신의 공부 시간에 한계가 있다는 것을 깨달았다.
• 그래서, 공부 시간의 한계를 초과하지 않으면서 과목의 중요도 합이 최대가 되도록 몇 개만 선택하여 수강하기로 마음먹었다.
• 중요도가 최대가 되도록 과목을 선택했을 때, 최대가 되는 중요도를 출력하는 프로그램을 작성하시오.

입력

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

출력

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

# 접근 방법

• 배낭 문제(냅색)과 동일한 문제이다.
• DP를 이용하여 풀어줄건데 DP[I][J] = i번째 까지의 과목에서, j시간을 공부에 할애할 수 있을 때 최대 중요도를 기록해준다.
• 따라서, time[i] > j => 현재 과목을 수강할 시간이 부족하다면 dp[i][j] = dp[i-1][j]이고
• 수강 가능하다면, dp[i][j] = max(dp[i-1][j-time[i] + val[i], dp[i-1][j])가 된다.

# 처음 풀이

• 위의 로직대로 했을 때 4480ms가 나왔다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

N, K = map(int, input().split())
dp = [[0] * (N+1) for _ in range(K+1)]
val, time = [0], [0]
for _ in range(K):
    a, b = map(int, input().split())
    val.append(a)
    time.append(b)

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]] + val[i], dp[i-1][j])

print(dp[K][N])

# 다음 풀이

• 시간을 조금더 줄여보기 위하여 고민하였다.
• 우선, 2차원 배열로 생성되는 dp를 할애할 수 있는 시간+1 크기의 1차원 배열로 줄여주었다.
• 또한 과목의 정보를 입력받을 때마다 아래 로직을 수행해주었다.
  • for 문을 N에서 현재 과목에 필요한 시간 -1(time)까지 -1씩 순회해준다.
  • dp[t - time] + 현재 과목의 중요도가 현재 dp[t]보다 크다면 갱신해준다.
• 즉, 최대로 사용할 수 있는 시간이 20이며, 현재 과목에 5의 집중력이 필요하다고 생각해보자.
• N=20, time = 5이므로, dp[20-5] => dp[15]는 현재 과목을 수강하기 위해 직전 과목까지 들을 수 있는 최대의 시간이다.
• 로직을 변경한 결과 680ms까지 시간을 줄일 수 있었다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
def main():  
    N, K = map(int, input().split())  
    dp = [0] * (N+1)  

    for _ in range(K):  
        val, time = map(int, input().split())  
        for t in range(N, time - 1, -1):  
            now = dp[t-time] + val  
            if now > dp[t]:  
                dp[t] = now  
    print(dp[N])  

main()