[백준/JAVA] 7579_앱

백준🔗

7579번: 앱

 

문제

 

 

간단 풀이

어제 배낭문제와 비슷한 dp를 풀었었는데, 오늘도 비슷한 유형의 문제를 연습해 봤다.

사실 비슷한 유형이라 금방 풀 줄 알았는데 좀 헤매느라 생각보다 시간이 오래 걸렸다ㅠㅠ

 

👇dp 설명은 어제 풀었던 문제 참고!!

2023.06.18 - [알고리즘/백준] - [백준/JAVA] 20303_할로윈의 양아치

 

이번 문제는 메모리와 비용을 가진 앱들을 선택해서 최소 비용으로 M 이상의 메모리를 확보하는 것이 목표다.

그래서 처음에 나는 dp테이블 정의를

dp[i][j] : 앱이 1~i번까지 있고, j만큼의 메모리를 확보하기 위해 필요한 앱 비활성화의 최소 비용

..으로 정의했다. 

결론적으로 이렇게 정의해서는 답을 낼 수 없었는데,

M의 범위가 최대 1000만이기 때문에 dp테이블을 채울 때 앱마다 1000만번씩 연산을 수행하는 것도 비효율적인 일이고, 심지어 'M이상'의 메모리를 확보해야 하기 때문에 dp테이블을 더 크게 만들어야 한다면 그 범위를 어떻게 지정해야 할지도 알 수 없었다.

또한 '최소' 비용을 구해야 하기 때문에, 이전에 배낭 문제에서는 배낭 문제에 담을 수 있는 '최대' 가치를 구하는 상황과도 맞지가 않아서 dp테이블을 제대로 만들기가 쉽지 않았다.

그래서 어떻게 해야 하는지 고민을 했고 다른 코드들도 참고해 봤는데..

 

dp[i][j] : 앱이 1~i번까지 있고, j만큼의 비용을 사용했을 때 확보할 수 있는 최대 메모리

이렇게 dp테이블의 정의를 쉽게 풀 수 있었다.

앱이 최대 100개, 앱 1개당 최대 비용이 100이기 때문에 비용의 총합은 최대 10000으로 범위가 정해지게 된다. 

메모리가 M이상인 경우의 비용들만 비교해서 그 중 최소 비용을 출력하면 우리가 찾는 답이 된다. 

 

 

코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); // 활성화된 앱 개수
		int M = Integer.parseInt(st.nextToken()); // 추가로 필요한 메모리
		// 활성화된 앱들의 메모리&비용 입력받기
		StringTokenizer st1 = new StringTokenizer(br.readLine());
		StringTokenizer st2 = new StringTokenizer(br.readLine());
		int[] memory = new int[N + 1];
		int[] cost = new int[N + 1];
		int sumM = 0;
		for (int i = 1; i <= N; i++) {
			memory[i] = Integer.parseInt(st1.nextToken());
			cost[i] = Integer.parseInt(st2.nextToken());
			sumM += memory[i];
		}
		// dp[i][j] : 1~i번 앱이 있고, j만큼의 비용을 사용하여 확보할 수 있는 메모리
		// 1차원으로 풀자
		int[] dp = new int[10001];
		int minCost = 10000;
		for (int i = 1; i <= N; i++) {
			for (int j = 10000; j >= cost[i]; j--) {
				dp[j] = Math.max(dp[j], dp[j - cost[i]] + memory[i]);
				if (dp[j] >= M) {
					minCost = Math.min(minCost, j);
				}
			}
		}
		System.out.println(minCost);
	}
}

 

참고 자료

[백준 7579 : JAVA] 앱 / Dynamic Programming