[코딩 테스트] 2026-03-27 — 0/1 배낭 문제

오늘의 문제 선정 이유

 

AI 도구와 학습 플랫폼이 다시 주목받는 흐름 속에서, 제한된 자원 안에서 최대 효과를 고르는 0/1 배낭 문제는 여전히 실무형 사고력을 잘 보여주는 대표 DP 유형이기 때문입니다.

문제 설명

한 개발자는 하루 공부 시간이 W시간뿐이다.
오늘 공부할 수 있는 후보 주제는 N개가 있다. 각 주제는 공부에 필요한 시간과, 공부했을 때 얻는 점수가 정해져 있다.

각 주제는 최대 한 번만 공부할 수 있다.
하루 공부 가능 시간 W를 넘지 않으면서, 얻을 수 있는 점수 합의 최댓값을 구하라.

첫째 줄에 주제 개수 N, 하루 공부 가능 시간 W가 주어진다.
둘째 줄부터 N개의 줄에 걸쳐 각 주제의 공부 시간 time, 점수 score가 주어진다.

입출력 예시

[text]입력:
4 7
6 13
4 8
3 6
5 12

출력:
14

설명:
공부 시간 4인 주제와 3인 주제를 선택하면 총 7시간, 점수 14로 최대이다.

[text]입력:
5 10
2 3
3 4
4 8
5 8
9 10

출력:
16

설명:
공부 시간 5인 주제와 4인 주제, 1개 더 넣는 조합은 불가능하다.
시간 2, 3, 5를 선택하면 총 10시간, 점수 15다.
시간 2, 4, 5는 11시간이라 불가능하다.
최대는 시간 2, 3, 4를 선택한 점수 15가 아니라,
시간 4, 5를 선택한 점수 16이다.

[text]입력:
3 5
6 10
7 13
8 20

출력:
0

설명:
모든 주제가 공부 가능 시간을 초과하므로 아무것도 선택할 수 없다.

제약 조건

• 1 <= N <= 100

 

• 1 <= W <= 10000

 

• 1 <= time <= W 또는 time > W일 수 있음

 

• 1 <= score <= 100000

 

• 시간 제한: 1초 ~ 2초

 

• 각 주제는 최대 1번만 선택 가능

풀이 접근법

핵심 아이디어

이 문제는 각 주제를 선택할지 말지 두 가지 경우로 나뉜다.
모든 경우를 직접 만들면 경우의 수가 너무 많다. 그래서 dp[w] = 공부 시간 w 안에서 얻을 수 있는 최대 점수로 정의하면, 이전 상태를 재사용하면서 빠르게 답을 구할 수 있다.

0/1 배낭 문제에서는 같은 주제를 여러 번 쓰면 안 된다.
그래서 각 주제를 처리할 때 w를 큰 값부터 작은 값으로 거꾸로 순회해야 한다.

단계별 풀이 과정

1. dp 배열을 길이 W + 1로 만들고, 모두 0으로 초기화한다.
2. 각 주제 (time, score)를 하나씩 확인한다.
3. 현재 주제를 사용할 수 있는 시간 w에 대해 W부터 time까지 거꾸로 순회한다.
4. dp[w]와 dp[w - time] + score 중 더 큰 값을 저장한다.
5. 모든 주제를 처리한 뒤 dp[W]가 정답이다.

코드 풀이

Python

 

[python]import sys


def solve():
    input = sys.stdin.readline
    N, W = map(int, input().split())

    dp = [0] * (W + 1)

    for _ in range(N):
        time, score = map(int, input().split())

        # 같은 주제를 여러 번 쓰지 않기 위해 뒤에서부터 갱신한다.
        for w in range(W, time - 1, -1):
            dp[w] = max(dp[w], dp[w - time] + score)

    print(dp[W])


if __name__ == "__main__":
    solve()

JavaScript

 

[javascript]const fs = require("fs");
const input = fs.readFileSync(0, "utf8").trim().split("\n");

function solve() {
  const [N, W] = input[0].split(" ").map(Number);
  const dp = Array(W + 1).fill(0);

  for (let i = 1; i <= N; i++) {
    const [time, score] = input[i].split(" ").map(Number);

    // 같은 주제를 여러 번 선택하지 않기 위해 뒤에서부터 갱신한다.
    for (let w = W; w >= time; w--) {
      dp[w] = Math.max(dp[w], dp[w - time] + score);
    }
  }

  console.log(dp[W]);
}

solve();

시간·공간 복잡도

• 시간 복잡도: O(N * W) — 각 주제마다 가능한 모든 공부 시간을 한 번씩 확인한다.

 

• 공간 복잡도: O(W) — 1차원 dp 배열만 사용한다.

틀리기 쉬운 포인트

• w를 작은 쪽에서 큰 쪽으로 순회하면, 같은 주제를 여러 번 사용한 것처럼 계산된다.

 

• dp[N][W] 형태의 2차원 DP로도 풀 수 있지만, 메모리를 아끼려면 1차원으로 줄일 수 있다.

 

• 정답은 꼭 dp[W]만 보면 된다. W 이하에서 가능한 최대값이 갱신되어 누적되기 때문이다.

유사 문제 패턴

• 예산 제한 안에서 광고 채널을 선택해 최대 효과를 만드는 문제

 

• 제한된 서버 자원 안에서 작업들을 골라 최대 처리 가치를 만드는 문제

 

• 여행 일정 시간 안에서 방문 장소를 선택해 만족도를 최대화하는 문제