메모리 최적화 DP

예제 데이터를 사용하여 점화식을 설명하겠습니다.

예제 데이터

• 앱의 개수 $ N = 5 $
• 확보해야 하는 메모리 $ M = 60 $
• 각 앱이 사용 중인 메모리 $ \text{memory} = [30, 10, 20, 35, 40] $
• 각 앱을 비활성화하는 데 드는 비용 $ \text{cost} = [3, 0, 3, 5, 4] $

초기화

먼저, dp 배열을 초기화합니다.

total_cost = sum(cost)  # 비용의 총합, 이 예제에서는 15
dp = [0] * (total_cost + 1)  # dp 배열 초기화, 길이는 16

점화식 적용

1. 첫 번째 앱 $i = 0$:

   • 메모리: 30, 비용: 3

   for cost in range(15, 3 - 1, -1):
       dp[cost] = max(dp[cost], dp[cost - 3] + 30)
   

   • dp 배열 갱신:

     • $ dp[15] = max(dp[15], dp[12] + 30) = max(0, 30) = 30 $
     • $ dp[14] = max(dp[14], dp[11] + 30) = max(0, 30) = 30 $
     • …
     • $ dp[3] = max(dp[3], dp[0] + 30) = max(0, 30) = 30 $

   • 갱신 후 dp 배열:

     dp = [0, 0, 0, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30]
     

2. 두 번째 앱 $i = 1$:

   • 메모리: 10, 비용: 0

   for cost in range(15, 0 - 1, -1):
       dp[cost] = max(dp[cost], dp[cost - 0] + 10)
   

   • dp 배열 갱신:

     • $ dp[15] = max(dp[15], dp[15] + 10) = max(30, 40) = 40 $
     • $ dp[14] = max(dp[14], dp[14] + 10) = max(30, 40) = 40 $
     • …
     • $ dp[0] = max(dp[0], dp[0] + 10) = max(0, 10) = 10 $

   • 갱신 후 dp 배열:

     dp = [10, 10, 10, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40]
     

3. 세 번째 앱 $i = 2$:

   • 메모리: 20, 비용: 3

   for cost in range(15, 3 - 1, -1):
       dp[cost] = max(dp[cost], dp[cost - 3] + 20)
   

   • dp 배열 갱신:

     • $ dp[15] = max(dp[15], dp[12] + 20) = max(40, 60) = 60 $
     • $ dp[14] = max(dp[14], dp[11] + 20) = max(40, 60) = 60 $
     • …
     • $ dp[6] = max(dp[6], dp[3] + 20) = max(40, 60) = 60 $
     • $ dp[5] = max(dp[5], dp[2] + 20) = max(40, 30) = 40 $
     • $ dp[4] = max(dp[4], dp[1] + 20) = max(40, 30) = 40 $
     • $ dp[3] = max(dp[3], dp[0] + 20) = max(40, 30) = 40 $

   • 갱신 후 dp 배열:

     dp = [10, 10, 10, 40, 40, 40, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60]
     

4. 네 번째 앱 $i = 3$:

   • 메모리: 35, 비용: 5

   for cost in range(15, 5 - 1, -1):
       dp[cost] = max(dp[cost], dp[cost - 5] + 35)
   

   • dp 배열 갱신:

     • $ dp[15] = max(dp[15], dp[10] + 35) = max(60, 95) = 95 $
     • $ dp[14] = max(dp[14], dp[9] + 35) = max(60, 95) = 95 $
     • …
     • $ dp[8] = max(dp[8], dp[3] + 35) = max(60, 75) = 75 $
     • $ dp[7] = max(dp[7], dp[2] + 35) = max(60, 45) = 60 $
     • $ dp[6] = max(dp[6], dp[1] + 35) = max(60, 45) = 60 $
     • $ dp[5] = max(dp[5], dp[0] + 35) = max(40, 45) = 45 $

   • 갱신 후 dp 배열:

     dp = [10, 10, 10, 40, 40, 45, 60, 60, 75, 95, 95, 95, 95, 95, 95]
     

5. 다섯 번째 앱 $i = 4$:

   • 메모리: 40, 비용: 4

   for cost in range(15, 4 - 1, -1):
       dp[cost] = max(dp[cost], dp[cost - 4] + 40)
   

   • dp 배열 갱신:

     • $ dp[15] = max(dp[15], dp[11] + 40) = max(95, 135) = 135 $
     • $ dp[14] = max(dp[14], dp[10] + 40) = max(95, 135) = 135 $
     • …
     • $ dp[4] = max(dp[4], dp[0] + 40) = max(40, 50) = 50 $

   • 갱신 후 dp 배열:

     dp = [10, 10, 10, 40, 50, 45, 60, 60, 75, 95, 95, 135, 135, 135, 135]
     

결과 계산

필요한 메모리 $ M = 60 $ 이상을 확보하기 위해 최소 비용을 찾습니다.

for cost in range(total_cost + 1):
    if dp[cost] >= M:
        print(cost)
        break

• dp[6]에서 이미 60 메모리를 확보할 수 있으므로 최소 비용은 6입니다.

결론

위 과정을 통해 비용이 최소인 메모리 확보 방안을 찾을 수 있습니다. 이를 통해 동적 프로그래밍을 활용하여 문제를 효율적으로 해결할 수 있습니다.