[백준: Java] 7579 - 앱

[문제]

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

 

앞선 설명이 장황하지만, 메모리는 주어진 메모리에 맞추면서 비용은 최소화하는 최적화 문제입니다. 최근에 응시한 코딩테스트에서 냅색 문제가 출제되었기 때문에 해당 풀이 방식으로 접근하였습니다.

---

[초기화]

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st, st1, st2;
	static int n, m;  // n개의 앱, 필요한 m의 메모리
	static int[] a;
	static int[] c;
	static int[] table;
	static int answer = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		a = new int[n];  // 메모리
		c = new int[n];  // 비용
		st1 = new StringTokenizer(br.readLine());
		st2 = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(st1.nextToken());
			c[i] = Integer.parseInt(st2.nextToken());
		}
		
		table = new int[(100 * n) + 1];  // 최대 100의 비용을 n개를 가질 수 있음
		
		solve();
			
	}

 

비용을 무게, 메모리를 코스트로 두었습니다.

 

메모리는 n개가 주어지며 한 메모리당 크기는 100이므로 테이블을 최대 비용인 100 x n + 1의 크기로 초기화하였습니다. 해당 배열에 저장되는 값은 비용에 따른 총메모리입니다.

---

[풀이]

	static void solve() {
		for(int i = 0; i < n; i++)
			for(int j = (100 * n); j > c[i] - 1; j--) {
				table[j] = Math.max(table[j], table[j - c[i]] + a[i]);  // 특정 비용일 때 메모리의 최대
				if(m <= table[j])  // 임계값에 도달했을 때
					answer = Math.min(answer, j);  // 최소 비용 계산
			}
		
		System.out.println(answer);
	}

 

냅색 문제와 마찬가지로 각 값에 대해 최댓값부터 주어진 값까지 역순으로 탐색합니다. 탐색을 하며 비용에 따른 메모리를 최대로 만들어 냅니다.

 

이때 임계값을 넘으면 값을 지속적으로 검사해 최솟값이 유지되도록 합니다. 주의할 점은 피팅되는 M을 찾는 것이 아닙니다.

 

예를 들어, 다음과 같은 케이스를 고려할 수 있어야 합니다.

• M = 60
  • 확보된 메모리 = 60, 비용 10
  • 확보된 메모리 = 70, 비용 4

알고리즘의 흐름은 다음과 같습니다.

1. 순차적으로 앱 선택
2. 선택된 앱을 기준으로 최대 비용에서 해당 앱의 비활성 비용까지 탐색
   • 역으로 탐색하는 이유는 중복 선택을 막기 위함
   • 가령 앱이 하나이고 a = [30], c = [3], table = [0, 0, 0, 0, 0, 0, ...]일 때, 순방향을 탐색하게 되면 다음과 같은 상황이 발생
     • 비용이 3일 때
       • table[3] = Math.max(table[3], table[3 - c[0]] + a[0])
       • [0, 0, 0, 30, 0, 0, ...]
     • 비용이 6일 때
       • table[6] = Math.max(table[6], table[6 - c[0]] + a[0])
       • [0, 0, 0, 30, 0, 0, 60, ...]
   • 이미 앱을 비활성화했기 때문에 비용이 6일 때도 최대 메모리는 30이어야 하지만, 비활성 전 비용을 참고하는 로직상 이전 값을 그대로 참조하게 됨
3. 현재 비용(j)에서 선택된 앱(i)을 비활성할지(table[j - c[i]] + a[i]), 비활성하지 않을지(table[j]) 최적의 선택 수행
   • 여기서 j는 j 그 자체일 수도 있지만, 선택된 앱을 비활성했을 때 발생한 비용이 합산되어 만들어진 비용일 수도 있음
   • 그러므로 현재 앱을 선택하기 전 만들어 낼 수 있는 메모리(table[j - c[i]]를 보고 비활성했을 때 메모리를 합산한 것이 더 큰지 아닌지 결정
4. 그렇게 현재 비용을 구할 수 있는 최적의 메모리가 m 바이트 이상이라면 최소 비용을 갱신 

---

[전체 코드]

package 백준.골드;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_7579_앱 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st, st1, st2;
	static int n, m;  // n개의 앱, 필요한 m의 메모리
	static int[] a;
	static int[] c;
	static int[] table;
	static int answer = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		a = new int[n];  // 메모리
		c = new int[n];  // 비용
		st1 = new StringTokenizer(br.readLine());
		st2 = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(st1.nextToken());
			c[i] = Integer.parseInt(st2.nextToken());
		}
		
		table = new int[(100 * n) + 1];  // 최대 100의 비용을 n개를 가질 수 있음
		
		solve();
			
	}
	
	static void solve() {
		for(int i = 0; i < n; i++)
			for(int j = (100 * n); j > c[i] - 1; j--) {
				table[j] = Math.max(table[j], table[j - c[i]] + a[i]);  // 특정 비용일 때 메모리의 최대
				if(m <= table[j])  // 임계값에 도달했을 때
					answer = Math.min(answer, j);  // 최소 비용 계산
			}
		
		System.out.println(answer);
	}
}

---