백준 7579 앱 파이썬 풀이

난이도 : 골드3

풀이일 : 2404254

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

7579번: 앱

---

문제캡쳐

---

아이디어

• dp를 활용한다.
• 주어진 모든 비용의 합 크기로 dp 배열을 생성하고, 각 비용에서 확보할 수 있는 최대 메모리를 기록한다.
• 같은 비용을 가지는 앱이 있으므로, dp는 뒤에서부터 탐색한다.
• dp 갱신 시, 목표 메모리가 확보되는 가장 작은 수를 기록해 마지막에 출력한다.

---

전체 풀이코드

import sys

N, M = map(int, sys.stdin.readline().split())
memories = list(map(int, sys.stdin.readline().split()))
costs = list(map(int, sys.stdin.readline().split()))
dp = [0] * (sum(costs) + 1)  # 각 비용으로 확보할 수 있는 최대 메모리

idx = len(dp)  # M 이상 메모리 확보를 위한 최소 비용
for i in range(N):
    memory, cost = memories[i], costs[i]
    # dp 역순회하며 확보가능한 최대메모리 저장
    for j in range(sum(costs), cost - 1, -1):
        dp[j] = max(dp[j], dp[j - cost] + memory)
        # 현재 최소비용보다 적은 비용으로 M 이상 메모리 확보 가능 시
        if j < idx and dp[j] >= M:
            idx = j

print(idx)

---

세부 풀이코드

N, M = map(int, sys.stdin.readline().split())
memories = list(map(int, sys.stdin.readline().split()))
costs = list(map(int, sys.stdin.readline().split()))
dp = [0] * (sum(costs) + 1)  # 각 비용으로 확보할 수 있는 최대 메모리

• memories : 각 앱을 종료할 시 확보할 수 있는 메모리들을 저장하는 배열이다.
• costs : 각 앱을 재시작 할 때 필요한 비용들을 저장하는 배열이다.
• dp : 각 비용을 사용해 확보할 수 있는 최대 메모리를 저장하는 배열이다. 모든 비용을 더한 값까지 반영될 수 있도록 크기를 설정한다.

 

idx = len(dp)  # M 이상 메모리 확보를 위한 최소 비용
for i in range(N):
    memory, cost = memories[i], costs[i]
    # dp 역순회하며 확보가능한 최대메모리 저장
    for j in range(sum(costs), cost - 1, -1):
        dp[j] = max(dp[j], dp[j - cost] + memory)
        # 현재 최소비용보다 적은 비용으로 M 이상 메모리 확보 가능 시
        if j < idx and dp[j] >= M:
            idx = j

print(idx)

• idx : 목표 메모리를 확보할 수 있는 최소 비용을 저장할 변수이다.
• for i in range(N) : 주어지는 앱의 수 만큼 반복한다.
• for j in range(sum(costs), cost - 1, -1) : dp의 맨 뒤부터, 현재 cost까지 역순으로 반복문을 수행한다.
• dp[j] 에는 현재 저장되어 있는 최대 메모리의 값과, 현재 비용에서 cost를 뺀 위치에 저장되어 있는 최대 메모리에 현재 메모리를 더한 값 중 큰 것을 저장한다.
• 만약, 현재 저장되어 있는 최소 비용보다 적은 비용으로 목표 메모리 M 이상을 확보하는 것이 가능하다면, idx를 재할당한다.
• 저장되어 있는 idx를 출력한다.

---

코드 개선

• value error와 오답 이후 개선 과정을 기록하였습니다.

1차

import sys

N, M = map(int, sys.stdin.readline().split())
memories = list(map(int, sys.stdin.readline().split()))
costs = list(map(int, sys.stdin.readline().split()))
apps = []
dp = [0] * (sum(costs) + 1)

for i in range(N):
    apps.append((costs[i], memories[i]))
apps.sort()

idx = len(dp)
for cost, memory in apps:
    for i in range(sum(costs), cost - 1, -1):
        dp[i] = max(dp[i], dp[i - cost] + memory)
        if dp[i] >= M and i < idx:
            idx = i
            
print(idx)

• memories, costs를 묶어 각 앱의 메모리와 비용을 apps에 추가하고, 정렬 한다.
• 정렬 이후 이전 서술한 방식으로 반복을 수행한다.
• 처음에는 역순으로 반복문을 돌지 않았기 때문에, 앞 쪽부터 돌려고 정렬을 했었는데 변경하면서 쓸모없게 된 부분을 아직 정리하지 못한 상태의 코드였다. 

2차

import sys

N, M = map(int, sys.stdin.readline().split())
memories = list(map(int, sys.stdin.readline().split()))
costs = list(map(int, sys.stdin.readline().split()))
dp = [0] * (sum(costs) + 1)  # 각 비용으로 확보할 수 있는 최대 메모리

idx = len(dp)  # M 이상 메모리 확보를 위한 최소 비용
for i in range(N):
    memory, cost = memories[i], costs[i]
    # dp 역순회하며 확보가능한 최대메모리 저장
    for j in range(sum(costs), cost - 1, -1):
        dp[j] = max(dp[j], dp[j - cost] + memory)
        # 현재 최소비용보다 적은 비용으로 M 이상 메모리 확보 가능 시
        if j < idx and dp[j] >= M:
            idx = j

print(idx)

• 위에 설명한 코드다. 실행 결과 차이는 아래 사진처럼 별 차이 없다.

 

---

느낀점

• 이제 dp 문제에 익숙해지고 있나 싶었는데도 너무 오래 풀고 있는 걸 보니 아직 덜 익숙해진 것 같다. 조금 더 이피 문제들 찾아서 풀어야지