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번째 시간으로 듣지 못할 경우는
이전 과목의 우선도를 할당해줍니다.
'Language > JAVA' 카테고리의 다른 글
| [JAVA][백준 1092][Greedy, Sort] 배 - 컴도리돌이 (0) | 2022.08.17 |
|---|---|
| [JAVA][백준 8980][그리디, 정렬] 택배 - 컴도리돌이 (0) | 2022.08.16 |
| [JAVA][백준 12015][이분 탐색] 가장 긴 증가하는 부분 수열2 - 컴도리돌이 (0) | 2022.07.30 |
| [Java][백준 2470][투 포인터] 두 용액 - 컴도리돌이 (0) | 2022.07.29 |
| [JAVA][백준 2122][그리디 정렬] 센서 - 컴도리돌이 (0) | 2022.07.27 |
