[BOJ - JAVA] 7579 - 앱 (DP, 배낭 문제)

# 주소

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

7579번: 앱

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int m = scan.nextInt();
		int[] arr = new int[n];
		int[] ans = new int[n];
		for(int i = 0; i < n; i++)
			arr[i] = scan.nextInt();
		for(int i = 0; i < n; i++)
			ans[i] = scan.nextInt();
		int[][] dp = new int[n][10001];
		int answer = Integer.MAX_VALUE;
		for(int i = 0; i < n; i++) {
			int memory = arr[i];
			int cost = ans[i];
			for(int j = 0; j <= 10000; j++) {
				if(i == 0) {
					if(j >= cost)
						dp[i][j] = memory;
				}
				else {
					if(j >= cost)
						dp[i][j] = Math.max(dp[i - 1][j - cost] + memory, dp[i - 1][j]);
					else
						dp[i][j] = dp[i - 1][j];
				}
				if(dp[i][j] >= m)
					answer = Math.min(answer, j);
			}
		}
		System.out.println(answer);
	}

}

문제의 원리를 살펴보겠습니다.

# 접근법

입력값을 보면

5 60
30 10 20 35 40
3 0 3 5 4

으로 주어집니다.

여기서 N = 5, M = 60이고 MEMORY는 [30, 10, 20, 35, 40]이며 COST는 [3, 0, 3, 5, 4]가 됩니다.

문제에서 물어보는 것은, M >= 60을 만족하는 최소 COST의 합을 구해야 하는 것인데요.

N 값이 적으면 브루트포스로도 풀 수 있겠으나 N이 100까지 주어지기 때문에 DP방식으로 접근해야 합니다.

따라서 DP로 접근하기 위해 DP배열을 2차원으로 선언해야 하고 DP의 첫 번째 행은 Memory의 인덱스를 관리, 두 번째 행은 Cost의 비용을 담당합니다.

위의 예제로 생각을 해본다면, 최초에 dp[0 ][0]은 0번째 인덱스로 0의 비용을 만들 수 있는 값을 의미합니다.

dp[0][3]은 0번째 인덱스로 3의 비용을 만들 때의 비용합을 의미합니다.

자 그렇다면, 예제로 생각을 해봅시다.

Memory : [30, 10, 20, 35, 40]

COST : [3, 0, 3, 5, 4] 인 상에서

30이라는 값을 가지고 3의 비용이 드는데, 최초의 시행 경우에는 다른 값을 탐색할 이유가 없으므로 30을 유지합니다.

이후 i >= 1일 때에는

10의 memory를 탐색하는데에 0의 비용이 듭니다.

따라서, dp[1][j] = 값은 dp[0][j] + 10값이어야 합니다. 

이를 j는 0부터 8까지 나타내보면, 

-	0	1	2	3	4	5	6	7	8
dp[1][j]	10	10	10	40	40	40	40	40	40

이러한 양상이 나타나게 됩니다.

dp[2][j]는 어떨까요?

dp[2][j]는 2의 인덱스에 대 j의 비용으로 만들 수 있는 memory의 합이라고 말씀드렸습니다.

그렇기 때문에 dp[2][j]를 표로 나타내보면,

-	0	1	2	3	4	5	6	7	8
dp[2][j]	10	10	10	40	40	40	60	60	60

이 되는 것인데요. 왜 6에서 60이란 값이 나타날까요?

그 이유는 dp[2][6] = 인덱스 2개까지 탐색했을 때의 비용이 6이 되는 memory의 총합이 10 + 30 + 20 = 60(인덱스 1,2,3의 합)이기 때문에 그렇습니다.

즉, 7의 비용을 만들기 위해서도 60, 8의 비용을 만들기 위해서도 60이 들지만 현실적으로 7, 8을 만들 수 없기 때문에 최소의 비용 조건인 6만 가지고도 60을 채울 수 있게 되는 것입니다.

이는 수학에서 Lower-Bound라고도 부릅니다.

다시 돌아가, 이번엔 dp[3][j]에 대해 알아봅시다.

-	0	1	2	3	4	5	6	7	8
dp[3][j]	10	10	10	40	40	45	60	60	75

이렇게 나타낼 수 있습니다.

dp[3][8] = 75라는 값이 튀어나왔는데, 이는 3의 인덱스를 포함하여 총합을 구했을 때 8이라는 비용을 만들기 위해서 75라는 memory합이 나왔다는 것입니다.

이는 0번째 인덱스 + 1번째 인덱스 + 3번째 인덱스(30 + 10 + 35)의 합이며 8의 비용을 만들기 위한 최소값이 되는 것입니다.

로직을 보며 더 자세히 이해해보겠습니다.

for(int i = 0; i < n; i++) {
    int memory = arr[i];
    int cost = ans[i];
    for(int j = 0; j <= 10000; j++) {
        if(i == 0) {
            if(j >= cost)
                dp[i][j] = memory;
        }
        else {
            if(j >= cost)
                dp[i][j] = Math.max(dp[i - 1][j - cost] + memory, dp[i - 1][j]);
            else
                dp[i][j] = dp[i - 1][j];
        }
        if(dp[i][j] >= m)
            answer = Math.min(answer, j);
    }
}

메모리는 arr, cost는 ans에 받아오며 각 인덱스마다 탐색을 하여 dp의 최솟값을 구해봅시다.

2중 for문을 돌리는 것은, n값이 100밖에 안되기 때문이며 2번째 for문의 j값이 10000이 범위인 것은, cost의 최댓값이 10000이기 때문입니다.

i = 0일 때 j가 cost이상이면 memory값을 넣어주도록 하겠습니다.

i >= 1 일 땐 j가 cost 이상이면 memory값을 넣어야하는데, dp[i - 1]행의 [j - cost]열의 값에 메모리를 더한 값과 메모리를 넣지 않은 j열과 비교하여 dp를 갱신합니다.

그리고 j가 cost보다 적다면 dp[i - 1][j]값을 가져옵니다.

이후 정답이 될 answer를 계속해서 갱신하는데, answer는 j와 비교하여 가장 적은 비용으로 m이상이게 하는 j를 최솟값을 구합니다.

예제를 통해 알아낸 dp의 전체를 출력해보도록 하겠습니다.

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

이렇답니다.

조금 느낌이 오시나요?

결국 가장 빠르게 60이상을 찍은 열을 출력하는 문제라고 생각하시면 되겠습니다.

감사합니다.