[BOJ][Python3/PyPy3] 7579 - 앱

냅색 문제를 공부하고나서 도전했던 문제이다.

스스로 아이디어를 찾는데에 실패해서 결국 검색을 통해 해결했지만,

이 문제를 통해 얻어갈 수 있는 부분이 있었기에 정리하고자 한다.

 

어떤 앱을 실행시키기 위해서 추가로 M의 메모리를 확보해야 하는 상황이다.

따라서 이 메모리를 확보하기 위해 기존에 실행 중이었던 앱을 끄고자 한다.

실행 중인 앱을 한번 끄면 다시 키는데 드는 시간 등 추가 비용이 발생하게 된다.

이 비용을 수치화 할 수 있다고 가정하면

실행 중이던 어떤 앱을 껐을 때 얻을 수 있는 메모리가 m, 발생하는 비용이 c로 정해진다.

이제 N개의 앱이 주어진다. 각각의 앱마다 m, c 의 값을 갖는다.

 

이 문제는 M이상의 메모리를 확보하기 위해 필요한 최소 비용을 구하는 것이다.

---

아직 냅색문제가 익숙하지 않아서, 처음에는 냅색 문제를 공부할 때 봤던 예제

'평범한 배낭' 문제 풀이 아이디어를 참고하면서 식을 세웠다.

dp테이블은 다음과 같은 구조로 채우게 되었다.

 

dp[i번째 앱][추가로 확보해야하는 메모리] = 비용

 

i번째 앱까지 활성화/비활성화시켜서 '얻은 메모리'가 M일 때의 비용

이렇게 잡는 것을 떠올렸다.

그러나 우리의 목적은 최대한 M에 가깝게 최소 메모리를 확보하는 것이 아니라

메모리를 M보다 더 많이 확보해도 좋으니 어떻게든 비용을 최소화하는 것이다.

 

따라서 이렇게 생각할 경우 만들어야하는 dp테이블의 크기가 매우 커지게 된다.

그래서 거꾸로 '지금까지 확보한 메모리'가 아니라

'앞으로 확보해야 하는 메모리'를 변수로 넣을 생각을 했다.

 

앞으로 확보해야하는 메모리가 0이하가 되면

그때는 dp테이블에서 값을 찾아 채우는 것이 아니라

바로 자기 자신이 이미 정답 후보가 된 것이므로, 기존 정답군과 값을 비교하면 된다.

 

그러나 이렇게 생각해도 문제점은 남아있다.

앱의 수는 100개, 그리고 확보해야하는 메모리의 최대값은 1000만이다.

dp테이블의 크기가 100*10000000 = 10억이다.

이 사이즈면 메모리초과, 시간초과를 피할 수 없게된다.

 

결국 여기에서 막혀서 검색했다.

검색하고도 그 아이디어를 이해하는데 시간을 많이 쏟았다...

그렇게 이해한 아이디어는 발상을 전환하여

가능한 메모리대신 가능한 비용들을 테이블 인덱스로 넣는 것이었다.

---

처음엔 문제조건을 제대로 읽지 않아서 각 앱의 비용도 1000만까지 되는 줄 알았다.

다시 읽어보니 각 앱의 비용 제한은 100이 최대였다.

최대 100개의 앱, 각 앱의 최대 비용은 100

그렇다면 가능한 비용 합의 범위는 0부터 10000까지이다.

 

이 정도 사이즈면 충분히 테이블로 만들어 돌릴 수 있다.

 나는 dp[앱][비용] = 메모리 와 같은 2차원보다.

dp[비용] = 메모리 와 같은 1차원을 배열을 만들고

각 앱에대해서 반복문을 돌며 1차원 배열을 갱신하기로 결정했다.

 

기본적인 점화식은 다음과 같이 세웠다.

 

1. 만약 i번째 앱을 종료한 경우 want_cost의 비용으로 확보한 메모리

dp[want_cost] = dp[want_cost - cost[i] ] + memory[i]

 

2. 만약 i번째 앱을 종료하지 않는 경우의 want_cost의 비용으로 확보한 메모리

dp[want_cost] = dp[want_cost]

 

이 두가지 경우에 대해 최대값을 취하면 되므로

dp[want_cost] = max( dp[want_cost - cost[i] ] + memory[i], dp[want_cost] )

 

처음엔 이게 이해가 되지 않았다.

그래서 구체적인 예시와 함께 이해했다.

 

현재 구하려는 것이 "10"의 비용으로 확보할 수 있는 최대 메모리라고 해보자.

즉, 우리가 구하려는 값은 dp[10] 이다.

 

그리고 현재 종료를 할 지 말지 고민하는 앱에 대해

확보가능메모리는 20, 필요 비용은 5 라고 하자

 

그렇다면 원하는 최대 메모리는

 

이 앱을 종료한 결과로 10의 비용이 발생하게 됐을 때, 총 확보한 메모리

이 앱을 종료하지 않았을 때, 기존에 10의 비용으로 확보했던 메모리

 

중 최댓값이다.

 

"이 앱을 종료한 결과로 10의 비용이 발생하게 됐을 때" 라는 말은

이 앱의 종료로 인해 발생한 비용까지 합치고 나서 비용이 10이 된다는 말이다.

따라서 우리가 참고해야할 값은 dp[10 - 5] 의 메모리 값이다.

 

이 메모리 값에 이 앱의 종료로 확보하게 된 메모리를 더하면

이 앱을 종료해서 10의 비용을 지불하게 됐을 때 확보한 메모리가 된다.

dp[10 - 5] + 20

 

이 앱을 종료하지 않았을 때는 그냥 기존에 알고 있던 dp[10]의 값을 보면 된다.

따라서 dp[10] = max(dp[10 - 5] + 20, dp[10] ) 이 된다.

 

그러나 문제는 이 다음이었다.

---

나는 개인적으로 바텀업 방식을 선호했었다.

처음 DP를 배울 때 피보나치 수열을 통해 DP를 이해했기 때문에

바텀업 방식이 기존에 이해했던 부분과 잘 맞기도 했고,

거꾸로 생각하기보다 차례대로 생각하는게 편했기 때문이다.

 

그러나 이 문제를 보통의 바텀업 방식으로 구현하듯 구현하였을 땐 WA를 받았다.

for i in range(1, num_app):
    for j in range(cost_sum+1):
        if j-cost[i] < 0:
            continue
        dp[j] = max(dp[j], dp[j-cost[i]] + memory[i])

0부터 cost_sum 까지 반복문을 돌렸을 때 WA를 받는데,

예제 입력에도 문제가 없었고, 왜 틀렸는지 이해가 안됐었다.

거꾸로 돌리나 아래서부터 돌리나 차이가 없는 것 아닐까?

https://www.acmicpc.net/board/view/6667

글 읽기 - 어디서 틀린건지 모르겠네요..

질문게시판에서 그 답을 찾을 수 있었다.

 

한번 예제 입력 1번에 대해 0부터 cost_sum까지 반복문을 돌린 코드와

cost_sum부터 거꾸로 반복문을 돌린 코드의 dp를 비교해보자.

 

<0부터 채워나간 경우>

[10, 10, 10, 40, 50, 50, 60, 80, 90, 90, 100, 120, 130, 130, 140, 160]

 

<cost_sum부터 거꾸로 채운 경우>

[10, 10, 10, 40, 50, 50, 60, 80, 80, 85, 100, 100, 115, 115, 115, 135]

 

둘다 비용이 6일때부터 확보해야하는 메모리인 60을 확보하므로

겉보기엔 정답이 똑같게 나온다.

 

중간 과정들을 펼쳐보면 다음과 같다.

 

<정답>

[0, 0, 0, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30]
[10, 10, 10, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40]
[10, 10, 10, 40, 40, 40, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60]
[10, 10, 10, 40, 40, 45, 60, 60, 75, 75, 75, 95, 95, 95, 95, 95]
[10, 10, 10, 40, 50, 50, 60, 80, 80, 85, 100, 100, 115, 115, 115, 135]

 

<오답>

[0, 0, 0, 30, 30, 30, 60, 60, 60, 90, 90, 90, 120, 120, 120, 150]
[10, 10, 10, 40, 40, 40, 70, 70, 70, 100, 100, 100, 130, 130, 130, 160]
[10, 10, 10, 40, 40, 40, 70, 70, 70, 100, 100, 100, 130, 130, 130, 160]
[10, 10, 10, 40, 40, 45, 70, 70, 75, 100, 100, 105, 130, 130, 135, 160]
[10, 10, 10, 40, 50, 50, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160]

 

첫 줄부터 차이가 발생하는 모습을 보인다.

그렇다면 첫줄을 채우는 과정을 따라가보자.

 

첫번째 앱에 대해서 비용은 3, 확보하는 메모리는 30이다.

 

<오답>

비용이 0일 때 => 확보한 메모리는 0

비용이 1일 때 => 확보한 메모리는 0

비용이 2일 때 => 확보한 메모리는 0

위 3가지 경우에 대해서는 dp[want_cost - cost[i] ] 의 인덱스가 -이므로

메모리를 확보할 수 없다.

 

비용이 3일 때 => 확보한 메모리는

dp[3] = max ( dp[3 - 3] + 30, dp[3] )

= max( dp[0] + 30, dp[3] )

= max( 30, 0 )

= 30

 

현재 이 앱까지를 봤을 때

이 앱의 실행을 종료하는 편이 비용이 3일 때 확보하는 메모리 양을 더 눌려준다.

여기에서 "실행을 종료하는 편이 메모리의 양을 더 늘려주는 경우" 에 집중하자.

 

비용이 4일 때 => 확보한 메모리는 

dp[4] = max( dp[4 - 3] + 30, dp[4] )

= max( dp[1] + 30, dp[4] )

= max( 30, 0)

= 30

 

당연한 결과다.

비용이 5일 때도 같은 결과를 보일 것이다.

(비용이 5일 때도 최대 확보 가능한 메모리 양은 30이다.)

 

그러나 비용이 6일 때부터 문제가 발생한다.

dp[6] = max( dp[6 - 3] + 30, dp[6] )

= max( dp[3] + 30, dp[6] )

= max( 30 + 30, 0)

= 60

 

DP 3에서 미리 체크해서 수정하여 늘린 메모리양 30이

DP 6에서도 중복하여 작용하고 말았다.

따라서 비용이 6일 때도 최대 30밖에 메모리를 얻을 수 없지만

60을 얻을 수 있다고 잘못 기록하고 말았다.

 

이 문제를 해결하는 방법은 두가지이다.

 

1. 2차원 배열로 이전 앱의 상태를 가져온다.

1차원 배열을 사용하니 기존값을 가져오는게 아니라 갱신된 값을 가져오는 문제가 발생한다.

따라서 기존값을 저장하는 배열, 갱신된 값을 저장하는 배열을 구분하여 만들어서 가져오면 된다.

위 예시의 경우

[0, 0, 0, 0, ... , 0] 으로부터 값을 읽어와서

[0, 0, 0, 30, 30, 30, ... , 30] 이렇게 채우면 된다.

두번째 줄의 배열이 30의 값으로 갱신되어도,

이후에는 첫번째 줄의 배열로부터 0의 값을 가져오기 때문에

문제가 발생하지 않는다.

 

2. 뒤쪽 값부터 채운다.

앞쪽의 값에 의해 뒷쪽의 값이 결정되는 형태이므로,

앞쪽 값에 의해 변화한 뒤쪽의 값이 그보다 더 뒤쪽의 값을 결정할 때 영향을 준다.

따라서 앞쪽의 값이 변하기 전에 미리 뒤쪽의 값을 결정하면 된다.

즉, 뒤부터 채우면 된다.

 

하지만 2번 방법에 대해 이렇게만 설명하면 오해를 낳기 쉽다.

자칫하면 "피보나치 수열의 경우에도 dp[i] = dp[i-2] + dp[i-1] 과같은 점화식이니

앞쪽부터 채우면 문제가 생겨야 하는 것 아닌가?" 라고 생각하게 될 수도 있기 때문이다.

 

그러나 피보나치 수열의 경우는 이 문제와 상황이 조금 다르다고 할 수 있겠다.

'영향을 준다' 라는 말의 의미가 서로 다르기 때문이다.

 

피보나치 수열의 경우에는

앞에서 결정한 dp[i-2], dp[i-1] 의 값이 dp[i] 의 값에 영향을 주어야 하는 게 맞다.

그리고 위에서 피보나치 수열의 "영향"에 대한 개념이 이것이다.

(종속적인 상황)

 

그리고 이 문제의 경우에도

dp[want_cost - cost[i] ] + memory[i], dp[want_cost] 의 값이

dp[want_cost] 의 값에 영향을 주어야 하는게 맞다.

(종속적인 상황)

 

그러나 중요한 차이점은

만약 가능한 비용의 범위가

0부터 10이라고 한다면

 

첫번째 앱까지 활성화/ 비활성화 시켰을 때

비용이 0인 경우

비용이 1인 경우

비용이 2인 경우

.

.

.

비용이 10인 경우

 

이 각각의 비용에 대해서는 

비용이 0인 경우와 비용이 1인경우가 서로 영향을 주고 받으면 안된다.

즉 현재 앱의 상황에서의 각각의 비용에 대해서는 서로 "독립적인 상황"이다.

 

첫번째 앱까지에 대해서 비용이 3일 때 최대메모리를 보고,

비용이 3일때는 알았으니 제쳐두고,

이제는 비용이 6일때의 최대 메모리도 보고 싶은 것이다.

그런데 비용이 3일 때 알게된 값을 비용이 6일 때의 최대메모리를 보는데 사용한다?

비용이 3일 때 알게된, 제쳐뒀어야 할 값을 제쳐두지 않고 활용한 셈이다.

 

이런 의미에서 앞에서의 값이 뒤에서 영향을 준다고 한 것이다.

따라서 영향을 주고 받지 못하도록 애초에 뒤부터 갱신하는 방법을 채택할 수도 있는 것이다.

 

따라서 수정하여 AC를 받은 코드는 다음과 같다.

# 7579 앱
num_app, minimum = map(int, input().split())
memory = list(map(int, input().split()))
cost = list(map(int, input().split()))
cost_sum = sum(cost)
dp = [0 for _ in range(cost_sum+1)]

for i in range(num_app):
    for j in range(cost_sum, cost[i]-1, -1):
        dp[j] = max(dp[j], dp[j-cost[i]] + memory[i])

for i in range(cost_sum+1):
    if dp[i] >= minimum:
        print(i)
        break

이렇게 구현하면 메모리를 덜 쓴다는 장점이 있다.

그러나 앞서 말한 "각각의 비용에 대해 독립적인 상황"을 나타내는 코드는 아니다.

 

이 코드는 종속적인 상황을 뒤부터 돌면서 회피한 코드이다.

정말 독립적으로 값을 가져와서 채운 코드는 2차원 배열을 활용한 코드이다.

메모리 제한이 여유롭다면, 2차원 배열을 활용하는 것이 실수를 줄이는 확실한 방법일 것이다.