[백준] 7579번 : 앱 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

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

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 주어진 M 바이트 이상의 메모리를 추가로 확보할 때 드는 비용의 최솟값을 구하는 문제이다.

해당 문제는 배낭 문제(Knapsack Problem)와 유사하여 이와 관련된 다이나믹 프로그래밍(Dynamic Programming) 알고리즘을 사용하면 해결할 수 있다.

2차원 dp 배열을 생성하여 dp[i][j] 값에 i번째까지의 앱을 고려했을 때 j 비용만 들여 확보할 수 있는 최대의 메모리를 저장하면 된다.

비용의 최댓값은 모든 앱을 비활성화했을 경우 드는 비용이므로 모든 앱의 비용을 더해주면 된다.

처음 각 앱까지만 고려했을 때 비용에 따른 최대 메모리는 이전 앱까지만 고려했을 때 비용에 따른 최대 메모리로 저장할 수 있고, 이후 이전 앱까지만 고려했을 때 비용에 따른 최대 메모리와 이전 앱까지만 고려했을 때 해당 비용에서 현재 앱의 비용을 뺀 비용에 확보할 수 있는 메모리에 현재 앱의 메모리를 더한 값 중 더 큰 값을 구하여 저장한다.

만약 해당 배열의 값이 확보하고자 하는 메모리보다 많으면 이전까지 구했던 최소 비용과 해당 비용을 비교하여 더 작은 비용을 저장한다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 앱의 개수와 추가로 확보해야 하는 메모리를 입력받는다. N, M = map(int, sys.stdin.readline().split())
3. 각 활성화되어 있는 앱의 메모리를 입력받아 리스트로 저장한다. 이때 앱을 1번부터 지정하기 위해 제일 앞에 0을 추가해 준다. memories = [0] + list(map(int, sys.stdin.readline().split()))
4. 각 앱을 비활성화하기 위해 드는 비용을 입력받아 리스트로 저장한다. 이때도 마찬가지로 1번부터 지정하기 위해 제일 앞에 0을 추가해 준다. cost = [0] + list(map(int, sys.stdin.readline().split()))
5. 각 앱을 비활성화하며 드는 비용별 확보할 수 있는 메모리를 저장하기 위한 2차원 dp 배열을 생성하고 초기화한다. 이때 행은 각 앱의 개수만큼 인덱스를 가져야 하고, 열은 모든 앱의 비활성화 시 비용의 총합만큼 인덱스를 가져야 한다. dp = [ [0] * (sum(cost) + 1) for _ in range(N + 1) ]
6. 최종 정답을 저장할 변수를 생성하고 모든 앱의 비활성화 시 비용의 총합을 저장한다. answer = sum(cost)
7. 각 앱을 하나씩 불러오고 for i in range(1, N + 1)
   1. 비용 값도 하나씩 불러오며 해당 앱까지만 고려했을 때 해당 비용에서 확보할 수 있는 메모리의 양은 이전 앱까지만 고려했을 때 해당 비용에서 확보할 수 있는 메모리의 양으로 기본 설정한다. for j in range(sum(cost) + 1): dp[i][j] = dp[i - 1][j]
   2. 이번에는 비용 값을 해당 앱의 비용부터 하나씩 불러오며 for j in range(cost[i], sum(cost) + 1)
      1. 해당 앱까지만 고려했을 때 해당 비용에서 확보할 수 있는 메모리의 양은 이전 앱까지만 고려했을 때 해당 비용에서 확보할 수 있는 메모리와 이전 앱까지만 고려했을 때 해당 비용에서 현재 앱의 비용을 뺀 비용에 확보할 수 있는 메모리에 현재 앱의 메모리를 더한 값 중 더 큰 값을 저장한다. dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] + memories[i])
      2. 만약 현재 앱까지만 고려하고 현재 비용에 대해 확보할 수 있는 메모리가 최소로 확보해야 하는 메모리보다 많으면 이전 정답과 해당 비용 중 적은 값을 정답으로 저장한다. if (dp[i][j] >= M): answer = min(answer, j)
8. 최종적으로 모든 앱을 고려한 뒤 최종 정답을 출력한다. print(answer)

728x90

3. 소스코드

import sys

N, M = map(int, sys.stdin.readline().split())
memories = [0] + list(map(int, sys.stdin.readline().split()))
cost = [0] + list(map(int, sys.stdin.readline().split()))

dp = [ [0] * (sum(cost) + 1) for _ in range(N + 1) ]

answer = sum(cost)

for i in range(1, N + 1):
    for j in range(sum(cost) + 1):
        dp[i][j] = dp[i - 1][j]

    for j in range(cost[i], sum(cost) + 1):
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] + memories[i])
        if (dp[i][j] >= M):
            answer = min(answer, j)

print(answer)