[백준] 16493번 최대 페이지 수

https://www.acmicpc.net/problem/16493

이 문제는 각 챕터를 선택하여 주어진 일수 내에서 최대 페이지 수를 구하는 문제로, 0/1 배낭 문제(Knapsack Problem)와 유사합니다.

N, M = map(int, input().split())
chapters = [tuple(map(int, input().split())) for _ in range(M)]

dp = [0] * (N + 1)

for days, pages in chapters:
    for i in range(N, days - 1, -1):
        dp[i] = max(dp[i], dp[i - days] + pages)

print(dp[N])

코드 설명

1. 입력 받기:
   • N과 M을 입력 받습니다.
   • 각 챕터의 소요 일수와 페이지 수를 튜플로 받아 chapters 리스트에 저장합니다.
2. 동적 계획법(DP) 테이블 초기화:
   • dp 리스트를 크기 N + 1로 생성하고 0으로 초기화합니다.
   • dp[i]는 i일 내에 읽을 수 있는 최대 페이지 수를 의미합니다.
3. DP 테이블 업데이트:
   • 각 챕터에 대해 반복합니다.
   • 소요 일수 days부터 N일까지 역순으로 반복합니다.
     • 이는 한 챕터를 여러 번 선택하는 것을 방지하기 위해서입니다.
   • dp[i]를 현재 값과 dp[i - days] + pages 중 큰 값으로 업데이트합니다.
     • 즉, 현재 일수 i에서 현재 챕터를 선택했을 때와 선택하지 않았을 때의 최대 페이지 수를 비교합니다.
4. 결과 출력:
   • dp[N]을 출력하여 N일 내에 읽을 수 있는 최대 페이지 수를 나타냅니다.

알고리즘 설명

• 0/1 배낭 문제: 각 아이템(챕터)을 선택하거나 선택하지 않는 결정으로 최대 가치를 찾는 문제입니다.
• 동적 계획법: 작은 부분 문제의 해를 이용하여 큰 문제의 해를 구합니다.
• 역순 업데이트: 아이템이 한 번만 선택되도록 DP 테이블을 역순으로 업데이트합니다.

시간 복잡도

• O(M * N):
  • M은 챕터의 수로 최대 20입니다.
  • N은 남은 기간으로 최대 200입니다.
  • 따라서 총 연산 횟수는 약 4,000으로 효율적입니다.

사용된 자료구조

• 1차원 리스트 dp: DP 테이블로 사용되며, 인덱스는 남은 일수를 의미하고 값은 최대 페이지 수를 저장합니다.