[백준] 7579번 : 앱 (Python)

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

7579번: 앱

문제

입력 / 출력

풀이 과정

이 문제가 왜 배낭 문제인지 전혀 알지 못해서 해답을 봤습니다.

항상 이런 해답은 보고 나서야 깨닫는 것 같네요. 해답을 보지 않았다면 평생 못풀었을 수도...

이 문제를 배낭 문제 풀이 형식으로 바꾸면 쉽게 해결됩니다.

생각의 방향을 고친다면 풀이는 자연스럽게 이해됩니다.

풀이 이해가 되지 않는다면 평범한 배낭 문제부터 이해하셔야 합니다!

2023.05.01 - [분류 전체보기] - [Python] 백준 12865번 : 평범한 배낭

[Python] 백준 12865번 : 평범한 배낭

<발상의 전환>

최대 용량이 정해져있지 않은 배낭 문제라고 생각하시면 됩니다!

DP[n][cost] : n번째 앱까지 비용을 cost만큼 사용해서 얻을 수 있는 최대 메모리값

이 예제의 확보해야하는 메모리 M은 60이기 때문에

DP[-1] 일차원 배열을 앞에서부터 살펴보면서 처음으로 60보다 크거나 같아지는 지점! 의 비용을 찾으시면 됩니다.

 

소스 코드 (메모리 절약 버전, 자세한 설명은 여기로)

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(2)]
costs = sum(data[1])
trans = [tuple(x) for x in zip(*data)]

a = [0 for _ in range(costs+1)]
for i in range(N):
    byte, cost = trans[i]
    b = [0 for _ in range(costs+1)]
    for j in range(costs+1):
        if j >= cost:
            b[j] = max(a[j], a[j-cost] + byte)
        else:
            b[j] = a[j]
    a = b

for i in range(costs + 1):
    if a[i] >= M:
        print(i)
        break

알고 나면 허무한 DP의 세계...