[백준 - 7579번] 앱 - Java //Wello Horld//

이번에는 BOJ의 7579번 문제 "앱"을 풀어보도록 하자

일단, 문제가 매우 길다. 쉽게 설명해 주면 앱에 백그라운드에 사용되어지고 있는 메모리가 있고, 그 메모리를 처리하는데 비용이 드는데, 입력으로 앱의 개수 N이 나오고, 확보하기위한 메모리바이트 수인 M이 주어진다. 그 다음에, 앱의 개수 N개 만큼 사용중인 메모리의 바이트m이 차례대로 주어진다. 그리고, 앱의 개수 N개 만큼 메모리를 확보하기위해 앱을 비활성화 했을 때 드는 비용 c가 차례대로 주어진다. 출력으로는 필요한 메모리 바이트 수인 M을 확보하기 위한 최소의 비용을 구하면 된는 문제이다.

문제가 길긴하나, 푸는 방법은 간단한다.

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

public class sample {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        long M = Long.parseLong(st.nextToken());
        App[] apps = new App[N];
        st = new StringTokenizer(br.readLine());
        //입력을 받는 부분
        for(int i = 0; i < N; i++){
            apps[i] = new App(Long.parseLong(st.nextToken()), 0);
        }
        int allCost = 0;
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            apps[i].c = Integer.parseInt(st.nextToken());
            allCost += apps[i].c;
        }
        
        //전체비용만큼 dp를 할당시킴(자료형은 long -> 10,000,000)
        long[] dp = new long[allCost + 1];
        //전체적으로 훑어줌
        for(int i = 0; i < N; i++){
            for(int j = allCost; j >= apps[i].c; j--){
                dp[j] = Math.max(dp[j], dp[j - apps[i].c] + apps[i].m);
            }
        }
        //0부터 전체비용까지 루프를 돌림. dp[i]값이 M이넘을 때의 비용이 최소비용이므로, 루프를 멈춰줌. 
        for(int i = 0; i <= allCost; i++){
            if(dp[i] >= M){
                bw.write(i + "\n");
                break;
            }
        }

        bw.flush();
        br.close();
        bw.close();
    }

    static class App{
        long m;
        int c;
        public App(long m, int c){
            this.m = m;
            this.c = c;
        }
    }
}

 

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

7579번: 앱