[BOJ] 7579번 : 앱(DP, Knapsack)

목차

접근

배낭(Knapsack) 알고리즘 문제다.

배낭 알고리즘에 대해선 자세히 써놓았던 이전 아티클을 참고해보자.

2023.12.11 - [알고리즘(Algorithm)] - [BOJ] 12865번 : 평범한 배낭(DP, Knapsack)

 

해결

배낭 알고리즘은 대표적인 DP 문제로 축의 의미를 어떻게 정의할건지가 중요하다.

당연히 한 축은 탐새할 물건의 인덱스가 되어야 할 것이다.

나머지 한 축은 가치를 저장할 시점의 용량이 되어야하는데, 여기선 두 가지가 있다.

하나는 사용 중인 메모리 바이트 수(`M`) 다른 하나는 비활성화 했을 때의 비용(`C`) 다.

하지만 메모리 바이트 수를 축으로 삼자니 범위가 $ 1 \le M \le 10,000,000 $ 로 말이 안된다.

그럼으로 비활성화 했을 때의 비용을 다른 한 축으로 잡자.

 

문제에서 주어진 범위는 아래와 같다.

• 앱의 수 : $N(1 \le N \le 100)$
• 비활성화 비용 : $C ( 1 \le C \le 100)$ 

그럼 비활성화 비용 가능 수는 100개의 앱이 모두 100만큼의 비용이 든다고 치면 `100 * 100 = 10,000`로 배낭의 축으로 쓰기에도 범위는 괜찮은 것으로 판단된다.

 

예시 문제의 예제를 통해 업데이트 과정을 봐보자.

주어진 예제는 아래와 같다.

• 프로그램 메모리 : 30, 10, 20, 35, 40
• 비활성화 비용 : 3, 0, 3, 5, 4
• 필요 확보 메모리 : 60

예시 문제의 총 비용합은 `3+0+3+5+4=15`이다.

그럼 아래와 같은 DP 테이블을 만들 수 있다.

 

행은 주어진 프로그램의 인덱스의 의미고, 열은 해당 비용 시점이라고 생각하자.

그렇기에 열은 비용이 0일 때도 있으니 실제 생성할 땐, `전체 비용 + 1`개만큼 생성해야한다.

 

먼저 첫 프로그램(0행)부터 보자.

첫 프로그램은 비활성화 비용이 3 이다.

그럼 0행의 0, 1, 2 열은 프로그램을 비활성화할 수 없다. 그렇기에 모두 0만큼의 메모리가 반환된다.

 

이제 3 열이 되면, 3만큼의 비용을 충족하기에, 현재 프로그램 메모리 30만큼을 반환할 수 있다.

 

그럼 3열 뒤로 비용 4 ~ 15까지는 모두 30을 반환할 수 있을 것이다.

 

여기까진 어렵지 않게 이해할 수 있다.

 

그럼 두번째 프로그램(1행)을 보자.

두번째 프로그램은 비활성화 비용이 0이다.

그렇기에 처음 열부터 현재 프로그램 메모리인 10만큼을 반환할 수 있다.

 

근데 이제 비용이 3으로 오게 되면, 앞선 프로그램과의 선택권이 겹치게 된다.

그럼 고려할 사항이 생긴다.

• 앞서 담은 프로그램을 빼고, 현재 프로그램을 담는다.
• 앞서 담은 프로그램을 가지고 간다.
• 둘 중 가치가 더 큰 것을 이번에 업데이트 해준다.

근데 사실 여기선 비활성화 비용이 0이기에 둘 다 가지고 가면 된다. 그래서 40으로 업데이트가 된다.

이 뒤의 열 4 ~ 15까지 모두 똑같이 40이 될 것이다.(업데이트 조건이 같으니까)

 

 

이제 세번째 프로그램(2행)을 보자.

세번째 프로그램은 비활성화 비용이 3이다.

여기서부턴 주의할점이 조금씩 생긴다. 

위와 같은 과정으로 비활성화 비용이 3이니까 열 3 까지 업데이트가 안되겠네? 할 수 있지만, 두번째 프로그램이 비활성화 비용이 0이었다. 그럼 이번에도 반환된 메모리가 저장이 되어있어야한다.

그렇기에 업데이트를 진행할 때, 이젠 이전 프로그램과의 가치 비교가 필요하다.

그니까 업데이트가 가능하다면, 먼저 위와 같은 과정을 진행해서 현재 상태를 업데이트 해주고, 그 후에 현재 업데이트된 상태와 이전 프로그램에서의 가치 상태를 비교해서 최댓값을 가지고 있을 수 있도록 유지해주는 것이다.(이 이유는 배열을 초기화 시킬 때 0 혹은 다른 더 작은 값으로 초기화 할텐데, 이 과정을 진행해주지 않으면 조건이 되지 않을 때 초기값을 가지고 감으로써 진행에 문제가 생길 수 있다.)

 

이제 열 3으로 오면, 진짜 문제가 발생한다.

열 3에서 이전 프로그램까지 담았던 가치와, 이전 프로그램을 빼고, 현재 프로그램을 담았을 때 가치를 비교해야한다. 이전 프로그램에서 현재프로그램을 담을 수 있을 때 까지만 빼줘야한다. 이걸 수식으로 보면

$max(dp[2-1][3], dp[2-1][3 - 3(cost_2)] + memory[2])$ 이 될 수 있다.

실제 값으로 보면 $ max(40, 10 + 20) $ 이 된다.

 

그럼 40으로 업데이트가 될 것이다.

그 후 열 5까지는 쭉 40으로 업데이트가 되다가, 열 6에서 비용이 6으로 증가했음으로 이전 프로그램과 현재 프로그램까지 모두 담을 수 있게 된다.

 

수식으로 보면 아래와 같다.

$max(dp[2-1][6], dp[2-1][6 - 3(cost_2)] + memory[2])$

실제 값은 $max(40, 40 + 20) $ 으로 60이 된다.

 

이렇게 위와 같은 점화식을 통해서, 쭉 업데이트를 해나갈 수 있다.

그럼 전체 완성된 결과는 아래와 같다. 한 눈에 보기 편하게, 인덱스에 가치와 비활성화 비용을 붙여서 작성했다.

 

그럼 이제 최소가 될 때 비용은 모든 물건이 다 들어갔을 때인 dp의 마지막 행에서 `M`값을 넘는 최초의 비용(열 값)을 찾아서 출력해주면 된다.

예제에선 다섯 번째 줄(4번 인덱스)의 6열이 최초로 60을 넘는 값이기에, 정답은 6이 된다.

위의 글과 표를 보면서, 직접 눈으로 따라가면서 익혀보면 어렵지 않다는 것을 알 수 있다.

 

또한 이런 Knapsack 문제는 축으로 정할 것만 잘 정하고 점화식 접근을 잘 한다면, 그렇게 어려운 문제는 아닐 것 같다.

 

코드

N, M = map(int, input().split())
memory = list(map(int, input().split()))
C = list(map(int, input().split()))
total_cost = sum(C)
dp = [[0] * (total_cost+1) for _ in range(N)]

for i in range(N):
    for j in range(total_cost+1):
        if j - C[i] >= 0:
            dp[i][j] = max(dp[i-1][j], dp[i - 1][j - C[i]] + memory[i])
        dp[i][j] = max(dp[i][j], dp[i-1][j])

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