티스토리 뷰
수강신청
문제
n개의 강의가 있고 학점제한이 m일 때 최대로 수강할 수 있는 수강학점을 구하는 문제이다.
문제 풀이
동적계획법으로 \(dp[i][k] =\:i번\:째\:강의까지\:수강하고\:k학점\:들었을\:때\:최대\:수강학점\) 으로 정의하고 구현하면
\(O(NM)\) 에 해결 가능하다. 슬라이딩 윈도우 기법으로 공간 복잡도를 줄일 수 있다.
소스 코드
'PS > Codeground' 카테고리의 다른 글
| [코드그라운드 연습문제] 할인권 (0) | 2017.04.13 |
|---|---|
| [코드그라운드 연습문제] 부분배열 (0) | 2017.04.13 |
| [코드그라운드 연습문제] 그릇 모으기 (5) | 2017.04.12 |
| [코드그라운드 연습문제] 새로운 방 (0) | 2017.04.10 |
| [코드그라운드 연습문제] 김씨만 행복한 세상 (0) | 2017.04.10 |
댓글