BOJ 백준 20667 크롬

BOJ 백준 20667 크롬

 

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

 

[ 문제 요약 ]

- 크롬 탭이 여러 개 주어진다. 크롬 탭 하나가 지워질 때마다 얻는 CPU 사용량과, 메모리 사용량이 있고, 중요도도 있다.

- 탭을 몇 개 지워서 원하는 CPU 사용량과 메모리 사용량을 맞춰야 한다. 이때, 중요도의 합의 최솟값을 출력한다.

 

 

[ 테스트 케이스 설명 ]

4 8 3	// 총 크롬 탭수(1<=100), 목표CPU사용량(1<=1,000), 목표 메모리 할당량(1<=100,000)
4 1 1	// 총 탭수만큼 반복되며, 각각 얻는 CPU양, 메모리양, 우선순위(1<=5)값
4 2 2
7 1 2
7 3 3
// 답 : 3

 

 

 

[ 문제 풀이 ]

먼저 이 문제는 기본적인 배낭 문제를 알고 있어야 풀 수 있다. 배낭 문제는 반복문을 돌면서 dp 공간에 특정 값을 계속 갱신시켜 나가며 답을 구하는 것이다. 이 풀이는 기본적인 배낭 문제를 알고 있다는 가정하에 진행한다.

 

배낭 문제를 풀 때, 보통 dp 배열을 1차원, 또는 2차원, 3차원으로 표현해 구현하는데, 이 문제는 CPU 사용량 + 메모리 사용량 두 개에 대해서 구현해야 하기 때문에 2차원 배열 dp로 선언하는 것이 맞다.

 

그럼 각각 dp 배열이 무엇을 의미하게 해야 할까??

 

이것을 정할 때는 시간 복잡도를 고려해서 정한다. 시간 복잡도를 생각하지 않고 아주 단순하게 생각해서 배열을 만든다 치면 아래와 같이 할 수 있다.

 

dp[CPU 사용량][메모리 사용량] = 우선순위의 최솟값

 

위와 같이 생각하고 나서 시간 복잡도를 생각해 보아야 한다. 시간 복잡도는 최악의 경우로 계산한다. 위처럼 dp를 선언하면 목표 CPU 사용량이 1,000이고, 목표 메모리 할당량이 100,000일 때, 둘을 곱하면 1억이 나온다. 이 1억에, 크롬 탭 별로 돌아야 하기 때문에, 1억 * 최악의 크롭 탭 숫자 100을 곱하면.. 100억이 되어 시간 초과다. 그래서 아래와 같이 생각을 바꾼다.

 

dp[CPU 사용량][우선순위] = 최대 메모리 할당

 

CPU 사용량과 우선순위를 dp 배열의 논리적 값으로 놓고 각 배열에 저장되는 값은 최대 메모리 할당을 놓는 것이다. 그냥 메모리 할당이 아니라 최대 메모리 할당을 하는 이유는 목표로 하는 CPU 사용량과 메모리 할당량을 도달할 때 우선순위가 가장 작아야 하기 때문이다.

 

위와 같이 하면, 시간 복잡도는 1,000(최악의 목표 cpu) * 500(우선순위 최악의 합) * 100(최악의 탭 수) = 50,000,000이다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Node{
	int cpu, memory, priority;
	Node(int c, int m, int p){
		cpu = c;
		memory = m;
		priority = p;
	}
}
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());// 크롭탭수(1<=100)
		int C		= Integer.parseInt(st.nextToken());// 목표CPU사용량(1<=천
		// M에 1을 더하는 이유는 dp에서 유효한 값을 확인하기 위해 +1로 시작하기 때문에 최종 확인할 M도 +1을 하는것
		int M		= Integer.parseInt(st.nextToken()) + 1;// 목표메모리할당량(1<=십만)
		int psum	= 0;
		Node node[] = new Node[N];
		
		for(int i=0; i<N; i++)
		{
			st		= new StringTokenizer(br.readLine());
			int c	= Integer.parseInt(st.nextToken());// CPU(1<=목표CPU할당량)
			int m	= Integer.parseInt(st.nextToken());// 메모리(1<=목표메모리할당량)
			int p	= Integer.parseInt(st.nextToken());// 우선순위(1<=5)
			node[i] = new Node(c,m,p);
			psum	+= p;
		}
		
		// dp[cpu 사용량][우선순위] = 메모리 할당량의 최대
		int dp[][] = new int[C + 1][psum + 1];
		
		dp[0][0] = 1;// dp[0][0]에 1을 넣어 유효한 값임을 표현
		
		for(Node now : node)
		{
			for(int c=C; c>=0; c--)			// 역순으로 하는 이유는 현재의 수정이 미래에 영향을 주지 않기 위해
			{
				for(int p=psum; p>=0; p--)	// 역순으로 하는 이유는 현재의 수정이 미래에 영향을 주지 않기 위해
				{
					int nextC = Math.min(C,c + now.cpu);// cpu값이 목표 cpu값을 초과하지 못하게 함
					int nextP = p + now.priority;// 다음 우선순위 값
					if(dp[c][p] != 0) // 유효한 값일 때만 현재를 통해 다음을 갱신
						dp[nextC][nextP] = Math.max(dp[nextC][nextP], dp[c][p] + now.memory);	
				}
			}
		}
		
		for(int p = 1; p<=psum; p++)
		{
			if(dp[C][p] >= M)
			{
				System.out.print(p);
				return;
			}
		}

		System.out.print(-1);
	}
}

 

dp 갱신시 유효한 값일 때만 dp를 갱신해주어야 한다 그렇지 않으면 dp의 모든 값이 업데이트 되어 정확한 답을 구할 수 없다. 그래서 dp 전체를 -1과 같은 숫자로 덮어 씌우고 시작하거나 하는데, 나는 dp[0][0]을 1로 만들어 유효한 값을 1이상으로 표현했다. 그렇기에 최종 확인하려는 메모리 값도 +1을 해주어야 해서 M에 +1을 해주었다.