-
[백준 - 7579번] 앱 - Java //Wello Horld//Algorithm/BOJ(Baekjoon Online Judge) 2019. 7. 26. 15:54
이번에는 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; } } }
'Algorithm > BOJ(Baekjoon Online Judge)' 카테고리의 다른 글
[백준 - 3053번] 택시 기하학 - Java //Wello Horld// (0) 2019.07.26 [백준 - 1927번] 최소 힙 - Java //Wello Horld// (0) 2019.07.26 [백준 - 11653번] 소인수분해 - Java //Wello Horld// (0) 2019.07.26 [백준 - 1018번] 체스판 다시 칠하기 - Java //Wello Horld// (0) 2019.07.26 [백준 - 2164번] 카드2 - Java //Wello Horld// (0) 2019.07.26