[다이나믹 프로그래밍] 7579번 - 앱

[백준] 7579번 - 앱

(한줄평) 전에 풀었던 냅색 문제를 잘 이해했다면 어렵지 않게 해결핧 수 있었던 문제. 하지만 더 좋은 풀이를 생각해봐야할 문제로 다음에 다시 한번 풀어보면 좋을 것 같다.

 

유사 문제: 12865

https://hseungyeon.tistory.com/search/%EB%83%85%EC%83%89

공부

앱의 개수가 N, 필요한 메모리가 M일 때, 둘째 줄의 N개의 정수는 현재 활성화 되어 있는 앱 A1, ..., AN이 사용 중인 메모리의 바이트 수인 m1, ..., mN을 의미하며, 셋째 줄의 정수는 각 앱을 비활성화 했을 경우의 비용 c1, ..., cN을 의미한다

(단, 1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000,000이며, 1 ≤ m1, ..., mN ≤ 10,000,000을 만족한다. 또한, 0 ≤ c1, ..., cN ≤ 100이고, M ≤ m1 + m2 + ... + mN이다.)

필요한 메모리 M바이트를 확보하기 위한 앱 비활성화의 최소 비용을 구하는 문제로 냅색 문제에 해당한다.

---

(풀이1) 메모리 기준으로 최소 비용 계산

풀이 시간: 1시간 이내

1) 문제 해결 아이디어

최소 M 메모리이상으로 앱을 비활성화하는데 최소 비용을 구하는 문제 -> 최대 (모든 메모리의 합 - M) 메모리 이하로 앱을 활성화해놓는데 최대 비용을 구하는 문제로 바꾸어서 문제를 풀었다.

 

첫번째 오류. 메모리 초과

메모리 초과 문제가 떠서 dp 테이블을 1차원 리스트로 변경해서 해결했지만 시간초과 문제가 떴다.

 

두번째 오류. 시간 초과

2%까지 되다가 바로 시간 초과가 떠서 실패했는데 pypy3로 제출하니 통과했다.

 

<점화식>

2) 소스코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())  # 앱 개수, 최소 메모리
memory = list(map(int, input().split()))  # 활성화된 앱이 사용웅인 메모리
cost = list(map(int, input().split()))  # 앱을 비활성화할 때 비용
max_active = sum(memory) - M # 활성화 가능한 최대 메모리

# n * (max_active)
# d[앱][활성화 가능 메모리]
d = [0] * (max_active + 1)

for i in range(N):
  m = memory[i]  # 현재 앱의 활성화 메모리
  c = cost[i]    # 현재 앱의 비활성화 비용
  for j in range(max_active, m - 1, -1):
    # 1. 현재 앱 활성화
    d[j] = max(d[j-m] + c, d[j])

print(sum(cost) - d[max_active])
# 메모리 m바이트를 확보하기 위한 앱 비활성화의 최소 비용

(풀이2) 비용 기준으로 최대 메모리 수 계산

풀이 시간: 1시간 이내

1) 문제 해결 아이디어

풀이 1에서는 활성화 가능한 최대 메모리 수만큼 리스트를 생성했는데 사실 그렇게 하면 python3으로는 시간초과 문제를 해결할 수 없다. 일단 각 메모리가 10,000,000 이하이고 앱의 개수는 100개 이하로 최댓값 경우의 수를 고려하면 리스트의 크기가 너무 커진다. 그러므로 메모리가 아닌 비용을 기준으로 dp테이블을 생성해야 한다. 모든 앱을 다 비활성화하는 경우가 최대 비용이므로 sum(cost) + 1 의 크기로 dp테이블을 생성한다.

 

<점화식>

 

2) 소스코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())  # 앱 개수, 최소 메모리
memory = list(map(int, input().split()))  # 활성화된 앱이 사용웅인 메모리
cost = list(map(int, input().split()))  # 앱을 비활성화할 때 비용
s = sum(cost)  # 모든 비용의 합

# d[j]: j 비용으로 얻을 수 있는 최대 메모리
d = [0] * (s + 1)
result = 1e9  # 메모리 m바이트를 확보하기 위한 앱 비활성화의 최소 비용

for i in range(N):
  m = memory[i]  # 현재 앱의 활성화 메모리
  c = cost[i]    # 현재 앱의 비활성화 비용
  for j in range(s, 0, -1):
    # 현재 비용이 현재 앱의 비활성화 비용보다 크거나 같으면
    if j >= c:
      d[j] = max(d[j-c] + m, d[j])

    # 해당 메모리가 최소 메모리이상이면 최솟값 갱신
    if d[j] >= M:
      result = min(result, j)
    #print(d)

print(result)

주석처리된 부분을 해제하면 2차원 리스트에서는 어떤식으로 값이 기록될지 알 수 있다.

 

[참고] https://claude-u.tistory.com/445

#392 백준 파이썬 [7579] 앱 - 냅색 알고리즘