[PS] 백준7579 : 앱(Java)

문제

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

7579번: 앱

---

풀이

DP Knapsack 문제

접근법

전형적인 Knapsack문제라 처음 배열의 행을 최대 BYTE 수인 10,000,000으로 두고 풀이하려함.

 

하지만 시간복잡도가 N이 최대 100이라 O(NM)이면 1억을 넘기 때문에 시간초과가 나기에 포기.

 

두번째로는 1차원 dp배열의 값을 최대 비용으로 두고 접근.

해당 문제에서 앱은 최대 100개, 비용은 각 앱 당 최대 100까지 나오기 때문에 최대 10,000까지의 길이가 나오고 시간복잡도를 계산해보면 O(NM) : 100 * 10,000 ⇒ 10,000,000으로 주어진 1초안에 풀이가 가능.

 

풀이방식으로는

기존 0-1 Knapsack과 동일하게 각 앱에 대해서 해당 비용으로 만들 수 있는 최대 메모리값을 원소로 하여금 부분문제의 해를 메모이제이션하는 방식으로 풀이함.

 

주의할 점으로는 dp값 갱신에 있어서 앞에서부터 탐색하게 되면 뒤의 값을 갱신할 때 충돌이 일어나게 됨.

역순으로 dp배열 갱신이 이루어져야 이전 부분문제 해를 이용하게 될 때 값 충돌이 일어나지 않음.

 

💡 값 충돌 : 0-1Knapsack의 경우 담고 안담고의 차이인데 해당 문제 충돌이 발생하게 되면 값이 누적되서 최적해가 나올 수 없게 됨.

 

 

---

소스코드

import java.io.*;
import java.util.*;

//BOJ_7579 앱
public class Main {
    static int N, M, res;
    static int[][] item;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); //앱의 개수
        M = Integer.parseInt(st.nextToken()); //필요한 바이트 수

        item = new int[N][2];

        //필요한 바이트 수 입력
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            item[i][0] = Integer.parseInt(st.nextToken());
        }

        //비용 입력
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            item[i][1] = Integer.parseInt(st.nextToken());
        }

        //기존의 0-1 배낭 문제
        // -> 각 물건들을 비교해서 해당 물건을 넣었을 때가 최적이라면 값 갱신
        // 최적이 아니라면 이전 값을 재사용

        //접근법
        //구하고자 하는 바이트 M까지 각 바이트를 채우기 위한 최소비용을 구하는 것을 부분 문제로 두고 풀이.
        //각 앱들을 통해 확보할 수 있는 바이트 수와 최소값을 구하고 그 중 최소해를 찾는 풀이.

        //새로운 접근법 찾아서..
        //기존의 0-1과 달리 해당문제는 10일 때 해당 물건을 넣을 수 있는게 아니라 0~해당 물건까지의 값이 동일해지는 게문제
        //0-1처럼 풀기 위해서 변형이 조금 필요한데,

        //메모리의 값 자체가 최대 천만까지 나옴으로 행이나 열로 둘 수 없으니 cost를 행으로 두고 배열의 값을 메모리로 두고 풀이.
        //각 코스트 별로
        //cost i를 만족할 수 있는 최대 byte 수를 원소값으로

        int[] dp = new int[10001]; //결과로 나올 수 있는 최대 cost는 100(최대 cost) * 100(N)

//첫번째 접근 방식 : 각 비용 i에 대해서 앱들을 비교하여 나올 수 있는 최대 메모리를 구하는 방식
        //잘못된 접근인 이유 : 이전 부분문제의 해를 사용하는 것에 있어서 충돌 발생 가능하기 때문에 최적해가 구해지기 어려움
//        for(int i=1; i<10001; i++) {
//            dp[i] = dp[i-1];
//            for(int j=0; j<N; j++) {
//                int cost = item[j][1];
//                if(i >= cost) { //현재 아이템의 코스트를 뺀 값이 0이상일 경우
//                    dp[i] = Math.max(dp[i], dp[i-item[j][1]] + item[j][0]);
//                }
//            }
//        }

//두번째 접근 방식 : 충돌을 피하기 위해 끝에서부터 현재 앱의 비용까지 역순으로 해를 구하는 방식.
        //부분문제를 사용함에 있어서 이전 방식대로라면 비용이 0인 앱에 대해서 dp[0] = 10으로 갱신 이후에 dp[1]을 비교할 때 10을 더한 20이 들어가게 되는데
        //역순으로 하게되면 dp[0]은 아직 0인 그대로이기 때문에 정상적인 값인 10이 들어가게 됨.
        for(int i=0; i<N; i++) {
            for(int j=10000; j>=item[i][1]; j--) { //처음 접근은 j를 0부터 끝까지 비교하면서 이전 값을 재활용하는 것이였는데, 이러면 부분문제 해가 이상
                dp[j] = Math.max(dp[j], dp[j - item[i][1]] + item[i][0]);
            }
//            System.out.println(Arrays.toString(dp));
        }

        for(int i=0; i<=dp.length; i++) {
            if(dp[i] >= M) {
                res = i;
                break;
            }
        }

        System.out.println(res);

    }
}

 

---

정리

• 이번 문제를 풀기 전에 평범한 배낭, 동전과 같이 기본적인 Knapsack문제를 조금 풀이해보고 도전했는데 역시 응용문제라 그런지 많이 힘들었던 문제였음
• 내가 생각하는 Kanpsack문제라 하면 중요한 점은 배열의 행과 열, 그리고 각 격자에 들어가는 원소를 정의하는 부분이 전부라고 생각했는데 해당 문제에서 내가 잘못된 접근을 한 이유는 이런 정의하는 부분에 있어 역발상을 해보지 못했던 부분이라 생각함
• 그래도 조금씩 Kanpsack 알고리즘에 대해 알아가는 것 같아서 뿌듯…