[백준] 7579 : 앱 (파이썬)

Algorithm/DP

[백준] 7579 : 앱 (파이썬)

_은선_ 2024. 7. 24. 21:23

SMALL

DP / Knapsack 문제

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

냅색(Knapsack) 알고리즘

간단하게 말하면, 한 도둑이 훔치는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.

출처: 위키피디아

냅색 알고리즘은 담을 수 있는 물건이 나눌 수 있냐 없냐에 따라 나눈다.

담을 수 있는 물건이 나누어 질 때(설탕 몇 g 등): 분할가능 배낭문제(Fractional Knapsack Problem)
담을 수 있는 물건이 나누어 질 수 없을 때(담는다 or 안담는다): 0-1 배낭문제(0-1Knapsack Problem)

해당 문제는 0-1 배낭문제의 경우다.

일반적인 배낭 문제와 다른점

일반적인 배낭 문제

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

목표: 주어진 무게 제한(w) 내에서 최대 가치를 찾음. (평범한 배낭 문제에선 배낭에 넣을 물건들의 무게 <= 주어진 무게 제한 w)
- 즉, w가 배낭에 담을 수 있는 무게의 최댓값임 => 우리는 w보다 작거나 같게 배낭에 물건을 담으면 됐음.
문제 설정: 각 아이템마다 무게와 가치가 주어지고, 무게 제한 내에서 최대 가치를 찾음.
동적 프로그래밍 접근 방식: dp[i][w]는 첫 i개의 아이템 중에서 무게 w를 초과하지 않으면서 얻을 수 있는 최대 가치를 의미함.

이 문제

목표: 필요한 메모리(m)를 확보하기 위해 최소 비용을 찾음. (이 문제에선 확보해야 하는 메모리 >= 필요한 메모리 m)
- 즉, m이 앱의 비활성화에 필요한 메모리의 최솟값임 => 우리는 m보다 크거나 같게 앱을 비활성화 해야함.
문제 설정: 각 앱마다 메모리와 비활성화 비용이 주어지고, 최소 비용으로 필요한 메모리를 확보해야 함.
동적 프로그래밍 접근 방식: dp[i][c]는 첫 i개의 앱 중에서 비용 c를 초과하지 않으면서 확보할 수 있는 최대 메모리를 의미함.

-> 냅색 알고리즘은 가치의 합을 최대화하는 방법을 찾는 문제이므로, 이 문제에서 dp 배열을 설정할 때 또한 가치가 최대가 되도록 값을 설정해야 한다.

-> 따라서, dp[i][m]이 아닌 dp[i][c]가 돼야 하며, 두번째 for문도 memory를 도는 것이 아닌, cost를 돌아야 한다.

for i in range(1, n + 1):
# for j in range(1, m + 1): XXXXX
    for j in range(sum(cost) + 1):

-> 결론적으로 이 문제에선 최소 메모리 m을 확보하기 위해 최소 비용을 찾아야 하지만, 일반적인 냅색 알고리즘에 들어맞게 하려면 다음과 같이 문제를 바꿔볼 수 있다.

문제 : 필요한 메모리(m)를 확보하기 위해 최소 비용을 찾음.
변경 후 : 주어진 최소 비용(c) 내에서 / 주어진 최소 비용(c)를 넘지 않은 선에서 메모리의 최대 가치를 찾음.

하지만, 우리는 메모리의 최대 가치를 구할 필요 없이 최소 메모리 m만 만족하면 되므로, 다음과 같이 조건을 걸어주면 된다.

즉, 최소 메모리 m을 만족하는 순간의 cost j를 minCost(cost의 최소비용을 기록해뒀던 변수)의 값과 비교하고, 최솟값이라면 해당 변수를 업데이트해준다.

if dp[i][j] >= m:
    minCost = min(minCost, j)

왜 일반 배낭 알고리즘과 다르게 풀어야 하는가?

1. 목표의 차이

배낭 문제는 주어진 제한 내에서(<=) 최대 가치를 찾는 반면, 이 문제는 필요한 메모리를 확보하기 위해(>=) 최소 비용을 찾는 것이다. 따라서 접근 방식이 다르다.

2. 제약 조건의 차이

배낭 문제는 주어진 무게 제한 내에서 최대 가치를 찾기 때문에 무게를 기준으로 접근한다. 이 문제는 비용을 최소화하면서 필요한 메모리를 확보해야 하므로 비용을 기준으로 접근한다.

💡 풀이코드 (성공 - 2차원 배열)

import sys 

n, m = map(int, sys.stdin.readline().split())
memoryArr = list(map(int,sys.stdin.readline().split()))
cost = list(map(int,sys.stdin.readline().split()))


def bag(n, m, memory, cost):
# dp = [[0] * (sum(cost) + 1) for _ in range(n + 1)] -> cost가 0일 때, 최소비용이 되는 경우는 고려 X -> 83% 틀린 케이스 
    dp = [[0] * (sum(cost) + 2) for _ in range(n + 1)] 
    minCost = sys.maxsize

    for i in range(1, n + 1):
        for j in range(sum(cost) + 1):
            if j - cost[i - 1] < 0:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i - 1]] + memory[i - 1])
        
            if dp[i][j] >= m:
                minCost = min(minCost, j)

    print(minCost)

bag(n, m, memoryArr, cost)

주요 로직

1. 현재 앱의 비용이 앱 비활성화에 필요한 비용(cost)를 초과한 경우 (j - cost[i - 1] < 0)

-> 현재 앱을 비활성화 하지 못함.

-> 현재 앱을 제외하고 n-1개의 앱만을 사용하여 최대 비용을 채울 때의 값 = dp[i - 1][j]

2. 현재 앱의 비용이 앱 비활성화에 필요한 비용(cost)를 초과하지 않는 경우

-> 현재 앱을 비활성화 할지/말지를 정해야함.

-> 현재 앱을 비활성화 했을 때의 메모리가 최댓값이 된다면 포함해야하고, 그렇지 않다면 현재 앱을 비활성화 하지 말아야함.

-> max(현재 앱을 비활성화 하지 않을 때의 메모리의 합, 현재 앱을 비활성화 할 때의 메모리의 합)

-> max(현재 앱을 비활성화 하지 않을 때의 메모리의 합, 현재 앱을 제외하고 (최대비용 - 현재 비용)를 채울 때의 메모리의 합 + 현재 앱의 메모리)

= dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i - 1]] + memory[i - 1])

 for i in range(1, n + 1):
        for j in range(sum(cost) + 1):
            if j - cost[i - 1] < 0:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i - 1]] + memory[i - 1])
        
            if dp[i][j] >= m:
                minCost = min(minCost, j)

3. 필요한 최소 메모리를 만족하면서 최소 비용을 찾기 위한 조건식 추가

우리는 메모리의 최대 가치를 구할 필요 없이 최소 메모리 m만 만족하면 되므로, 다음과 같이 조건을 걸어준다.

즉, 최소 메모리 m을 만족하는 순간의 cost j를 minCost(cost의 최소비용을 기록해뒀던 변수)의 값과 비교하고, 최솟값이라면 해당 변수를 업데이트해준다.

if dp[i][j] >= m:
    minCost = min(minCost, j)

예외 처리

문제를 잘 읽어보면 비용의 범위는 0 ≤ c1, ..., cN ≤ 100이다.

따라서, 최소 메모리를 만족하면서 최소 비용이 0이 될 때에도 minCost에 값을 기록할 수 있도록 하기 위해 다음과 같이 변경해주었다.

두번째 for문의 범위를 기존 1 ~ sum(cost) -> 0 ~ sum(cost)까지 도는 것으로 변경해주었다.
cost = 0일 때에도 dp 배열에 기록하기 위해 dp 배열의 c 범위를 다음과 같이 1 늘려 주었다.
- [0] * (sum(cost) + 1) -> [0] * (sum(cost) + 2)

변경 전

def bag(n, m, memory, cost):
    dp = [[0] * (sum(cost) + 1) for _ in range(n + 1)]
    minCost = sys.maxsize

    for i in range(1, n + 1):
        for j in range(1, sum(cost) + 1):

변경 후

def bag(n, m, memory, cost):
    dp = [[0] * (sum(cost) + 2) for _ in range(n + 1)]
    minCost = sys.maxsize

    for i in range(1, n + 1):
        for j in range(sum(cost) + 1):