[BOJ_Python] 16493. 최대 페이지 수

문제

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

 

사용 알고리즘

0/1 Knapsack

 

풀이

고려사항

1. 현재 부분 집합 중 최대 페이지 수인지

 

후기

1. 이 문제의 keypoint는 현재 부분 집합을 기준으로 해당 챕터를 넣을지 여부를 선택하는 것이다.

챕터를 나눠 담을 수 없기 때문에 0/1 knapsack 알고리즘을 적용했다.

조건이 작기 때문에 시간복잡도 상 브루트포스 알고리즘 적용해도 풀리지만, 

효율적인 방식을 위해 0/1 knapsack 알고리즘을 적용했다.

 

2. 소요 시간을 늘려가며 부분집합을 만든 후

해당 챕터를 기준으로 소요 시간이 초과되는 지 확인한다.

이후, 초과 될 경우 넣지 않고,

초과 되지 않을 경우 넣는 것과 넣지 않는 것 중에

어떤 것이 더 많은 페이지 수를 가지게 될 지 확인하며 진행한다.

 

3. 여기서 주의할 것은 어떤 것이 knapsack의 알고리즘의 무게와 가치에 해당하는지이다.

이 문제의 경우 N과 M이 기본 알고리즘과 반대여서 한번 더 확인이 필요했다.

 

코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

# 챕터에 관한 소요되는 일 수 및 페이지 수 정보
info = [[0, 0]]
for _ in range(M):
    info.append(list(map(int, input().split())))

# knapsack 정보 업데이트
knapsack = [[0] * (N + 1) for _ in range(M + 1)]
for i in range(1, M + 1):  # 챕터 관련
    for j in range(1, N + 1):  # 소요 일수 관련

        # 소요 일수보다 기준이 작은 경우
        if j < info[i][0]:
            knapsack[i][j] = knapsack[i - 1][j]
        # 현재 챕터터에 관한 정보를 사용하는 경우
        else:
            # 사용하지 않는 경우, 사용하는 경우 비교
            knapsack[i][j] = max(
                knapsack[i - 1][j], info[i][1] + knapsack[i - 1][j - info[i][0]]
            )
print(knapsack[M][N])

 

결과