[백준] 단계별로 풀어보기(단계:23,동적 계획법 2,JAVA)7579번, 앱

문제 링크

7579번: 앱

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

 

---

접근 방법

동적계획법이란 위 문제와 같이 동일한 연산을 계속 반복하여 비효율적으로 코드가 실행되어 그것을 향상시키기 위하여반복되는 연산의 결과를 따로 저장하여 적재적소에 코드가 더 효율적으로 만드는 방법입니다.

 

이 문제에서 핵심은

 

1. 비활성하여 M크기만큼 공간을 확보해야 한다.

2. 공간 확보 가능한 경우에서 최소의 비용으로 비활성할 때 비용을 구해라.

 

단계별 풀어보기를 순차적으로 풀어보았다면 2가지 냅색 알고리즘 문제를 풀어보았을 것입니다.

 

[12865번 평범한 배낭]

[백준] 단계별로 풀어보기(단계:15,동적계획법1,JAVA)12865번, 평범한 배낭

 

[2629번 양팔저울]

[백준] 단계별로 풀어보기(단계:23,동적 계획법 2,JAVA)2629번, 양팔저울

 

 

메모리 탐색(DP, 냅색)

 

DP[i][j]:  i는 i이하의 바이트와 비용에 대응하는 값들, j는 만들어야 하는 비용으로 표현하며 값은 최대 확보가능한 공간을 저장하였습니다.

 

예제입력1

 

DP[2][3] : 비용 3으로 1 ~ 2번째 앱을 비활성이 가능할 때 최대 메모리 감소량

 

바이트 = 30, 10( i = 2,  1 ~ i의 대응 값들)

 

비용 = 3, 0(i = 2,  1 ~ i의 대응 값들)

 

값은 최대 확보 가능한 공간으로 비용 3 + 0 = 3으로 2개 모두 비활성 가능하여

 

30 + 10 = 40의 공간이 확보되어DP[2][3] = 40으로 표현할 수 있습니다.

 

표를 보여드리면서 설명하도록 하겠습니다.(보기 편하게 행의 값은 대응하는 비용의 값으로 표현하겠습니다.)

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
3(1)	0	0	30	0	0	0	0	0	0	0	0	0	0	0	0
0(2)	0	0	40	0	0	0	0	0	0	0	0	0	0	0	0
3(3)	0	0	40	0	0	60	0	0	0	0	0	0	0	0	0
5(4)	0	0	40	0	35	60	0	75	0	0	95	0	0	0	0
4(5)	0	0	40	40	35	60	80	75	75	100	95	115	0	0	135

 

DP[1][1]: 비용 3으로 1을 만들 수 없기 때문에 공간 확보가 불가능하여 0의 값을 저장하였습니다.

 

DP[2][3]: 비용 3, 0으로 만들 수 있으며 최대값은 3 + 0 = 30 + 10 = 40으로 값을 저장하였습니다.

 

위에 표를 보면 조건에 따라 값을 얻을 수 있는 공식을 얻을 수 있습니다.(DP[i][j]일 때)

 

1. i의 대응하는 비용 ≥ app[i][1]일 때, DP[i-1][j] 값과 i번째 메모리를 사용하고 난 남은 비용의 최대값의 합 중 큰 값을 저장합니다.

 

DP[i][j] = Math.max(DP[i-1][j], DP[i-1][j - app[i][1]] + app[i][0]);

 

DP[i-1][j - app[i][1]]  : i번째 메모리를 비활성하고 남은 비용에 대한 최대 메모리 값

 

app[i][0] : i번째 메모리를 비활성할 때 얻는 메모리 값

 

2. i의 대응하는 비용 < app[i][1] 일 때, i번째 메모리를 비활성하지 못하기 때문에 DP[i-1][j]의 값만 비교합니다.

 

DP[i][j] = DP[i-1][j]

 

 

 

배열을 완성시키면 이제 결과를 출력하면 됩니다.

 

결과는 모든 메모리에 사용해야 하기 때문에 DP[N][0~...]에서 M보다 크거나 같은 값이 저장되어 있는 첫 i의 값을 결과로 출력하면 됩니다.

 

예를 들어,

 

필요한 메모리가 80이면 위에 표에서

 

DP[N][7]에서 80보다 크거나 같은 값을 처음 마주하게 되는데 최소 비용 값이다.

 

j의 값은 0부터 증가하기 때문에 처음 만나는 값이 최소 비용의 값이 될 수 있습니다.

 

 

 

※ DP[N][비용의 합]으로 만들어주는 이유는 조건에서 만들 수 있는 최대의 비용은 주어진 앱을 모두 비활성화 할 때이기 때문입니다.

 

알고리즘의 과정

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 app배열을 초기화해주었습니다.
• DP[][] 값을 구하는 appTermination 함수를 만들었습니다.
• BufferedWriter에 DP[N][0~10000]에서 M보다 큰거나 같은 수를 얻는 첫 번째 배열의 열의 값을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• appTermination은 반복문과 위의 2가지 조건을 가지고 DP[][]을 완성시켰습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
    public static int[][] app;  //앱 메모리, 비용 저장 배열
    public static int[][] DP;  //만들 수 있는 비용마다 확보 가능한 최대 메모리 크기 저장 배열
    public static int N,M;
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는  BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //N : 앱의 개수, M : 적어도 확보해야 하는 메모리
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        //0 : 메모리, 1 : 비용
        app = new int[N+1][2];
        int sum = 0;
        st = new StringTokenizer(br.readLine(), " ");
        //앱의 메모리 입력
        for(int j=1;j<=N;j++){
            app[j][0] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine(), " ");
        //앱의 비용 입력
        for(int j=1;j<=N;j++){
            app[j][1] = Integer.parseInt(st.nextToken());
            sum += app[j][1];
        }
        //최대 비용 기준 DP[i][j] 설정 : i번째 앱까지 비활성가능할 때 비용이 j일 때 최대 줄일 수 있는 메모리 양 
        DP = new int[N+1][sum+1];
        appTermination(sum);
        //M만큼 메모리를 줄이며 최소 비용인 값 탐색
        for(int i=0;i<=sum;i++) {
            if(DP[N][i]>=M) {
                bw.write(String.valueOf(i));
                break;
            }
        }
        bw.flush();     //결과 출력
        bw.close();
        br.close();

    }
    //점화식을 통한 DP[i[j] 탐색하는 함수
    public static void appTermination(int size) {
        for(int i=1;i<=N;i++) {
            for(int j=0;j<=size;j++) {
                //비용이 j일 때 i번째 앱을 비활성 가능할 때
                if(j >= app[i][1]){
                    DP[i][j] = Math.max(DP[i-1][j], DP[i-1][j-app[i][1]] + app[i][0]);
                }else       //비용이 j일 때  i번째 앱을 비활성하지 못할 때
                    DP[i][j] = DP[i-1][j];
            }
        }
    }
}