[백준] 7579번 앱 _ Python

[초기 접근 방법]

당시 잘못된 접근법

     → dp[i][j] : i번째 앱까지 중 j byte를 얻는데 소모되는 최소 cost

 

그러나 i의 범위는 100, j의 범위는 1천만이었기에

dp[][] 를 계산하게 되면 시간∙공간 복잡도가 매우 높다.

따라서, "비용"을 배낭의 크기로 생각하고 접근하는 것이 효율적이다.

 

 

 

[생각]

- dp 배열 정의

     → dp[i][j] : i번째 앱까지 중 j 비용으로 얻을 수 있는 최대 byte 수

 

- 점화식

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

           현재 앱을 계속 활성화 시켰을 때의 byte  vs  cost를 소모하면서 비활성화 시켰을 때의 byte 비교

 

 

Knapsack 풀이와 똑같았다.

4달 전쯤 풀고, 재채점이 다시 되었는데 '틀렸습니다'를 받고 다시 풀어는데

 

문제에서 요구하는 조건에서 비활성화 했을 경우의 비용 c의 범위가 0부터 시작한다.

따라서 dp[i][j] 에서 j cost의 범위 설정을 0부터 설정해야 했는데

지난 풀이에서는 1부터 설정해, 틀린 풀이가 되었다.

 

 

 

[코드]

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

# 재채점. 비용 합이 0인 경우도 정답이 될 수 있으므로,
# dp[i][j]에서 j의 범위를 0부터 설정해야 한다.


# 메모리 개수, 필요한 바이트 수
N, M = map(int, input().split())

memory = [0] + list(map(int, input().split()))
cost = [0] + list(map(int, input().split()))
sumCost = sum(cost)

# dp[i][j] : i번째 메모리까지 보았을 때, n비용을 사용하면서 얻을 수 있는 최대 바이트 수
dp = [[0] * (sumCost + 1) for _ in range(N + 1)]
dp[0][0] = 0  # 0비용을 사용하면서 얻을 수 있는 최대 바이트 수는 '0'

# M바이트를 확보하는데 필요한 최소 비용
result = float('inf')

# 각 메모리마다 목표하고자 하는 sumCost까지의 dp[]를 갱신한다.
for i in range(1, N + 1):
    for j in range(0, sumCost + 1):
        # 현재 앱을 비활성화 할만큼 j가 충분하지 않을 경우 → i번째 앱 계속 활성화
        if cost[i] > j:
            dp[i][j] = dp[i - 1][j]
        # 비활성화 할 수 있을만큼의 j를 확보했을 때
        else:
            # 현재 앱을 계속 활성화 시켰을 때의 byte  vs  cost를 소모하면서 비활성화 시켰을 때의 byte 를 비교한다.
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] + memory[i])

        # 필요한 메모리 M을 충족시켰을 때, 최소 비용 구하기
        if dp[i][j] >= M:
            result = min(result, j)

if M != 0:
    print(result)
else:  # 필요한 메모리 수가 '0'일 때
    print(0)