[JAVA][백준 17845][배낭문제] 수강 과목

Language/JAVA

컴도리돌이 2022. 8. 2. 09:00

728x90

17845번: 수강 과목

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

www.acmicpc.net

17845번

DP문제 중에 knapsack 문제로 해결해야 합니다.

bag[M][N]을 1부터 M+1번째 과목들을 대상으로

최대 N시간을 써서 얻을 수 있는

가장 큰 중요도를 구해야 합니다.

현재 i번째 시간으로 들을 수 있을 경우

이전 과목을 들은 경우와 현재 i번째 시간 전 + 현재 i번째 우선도를 비교해서

최대 값으로 bag [i][j]를 갱신해줘야 합니다.

현재 i번째 시간으로 듣지 못할 경우는

이전 과목의 우선도를 할당해줍니다.

728x90