섹션 10 Dynamic Programming - 6. 최대점수 구하기(냅색 알고리즘)

설명

정보올림피아드 대회를 앞두고, 제한된 시간 안에 여러 문제 중 최대 점수를 얻기 위한 전략을 세우는 문제입니다.

• 각 문제는 점수와 소요 시간이 주어지고, 문제는 한 번만 풀 수 있습니다.
• 제한 시간 안에서 점수 총합을 최대화해야 합니다.

이 구조는 전형적인 0/1 Knapsack 문제입니다.

---

입력

• 첫 줄: 문제 수 N (1 ≤ N ≤ 50), 제한 시간 M (10 ≤ M ≤ 300)
• 이후 N줄: 각 줄에 문제의 점수와 소요 시간

---

출력

• 제한 시간 내에 얻을 수 있는 최대 점수

---

예시 입력

5 20
10 5
25 12
15 8
6 3
7 4

예시 출력

41

설명

• 25점(12분), 15점(8분) 조합 → 총 40점 (가능)
• 10점(5분), 15점(8분), 6점(3분) 조합 → 41점 (가능)
  → 따라서 정답은 41점

---

코드 구현

import java.util.*;

public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt(); // 문제 수
    int m = sc.nextInt(); // 제한 시간

    int[] dy = new int[m + 1]; // dp[i] = i분일 때 최대 점수

    for (int i = 0; i < n; i++) {
      int score = sc.nextInt();
      int time = sc.nextInt();

      // 0/1 Knapsack → 뒤에서부터 순회
      for (int j = m; j >= time; j--) {
        dy[j] = Math.max(dy[j], dy[j - time] + score);
      }
    }

    System.out.println(dy[m]);
    sc.close();
  }
}

---

코드 설명 (0/1 Knapsack 방식)

• dy[j]: 시간 j일 때 얻을 수 있는 최대 점수
• 각 문제는 한 번만 풀 수 있으므로 뒤에서부터 순회

핵심 점화식:

dy[j] = Math.max(dy[j], dy[j - time] + score);

• dy[j - time] + score: 지금 문제를 푼 경우
• dy[j]: 지금 문제를 안 푼 경우

→ 이 둘 중 더 큰 값을 선택

---

시간 복잡도

• O(N × M) = 50 × 300 = 15,000 → 충분히 빠름

---

냅색 문제 유형 참고

문제 유형	설명
0/1 Knapsack	각 문제를 한 번만 풀 수 있음 (0번 or 1번 선택)
Unbounded Knapsack	동전처럼 하나의 아이템을 여러 번 선택 가능 (무한히 사용 가능)

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런