[백준] 13910번: 개업 - java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {

	static int n;
	static final int MAX = 10001;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()); // 짜장면의 수
		int[] woks = new int[MAX];
		int[] dp = new int[n + 1]; // dp[i] => i개의 짜장면을 만들기 위해 드는 최소 요리 횟수
		Arrays.fill(dp, MAX);
		dp[0] = 0;
		woks[0] = 1;

		int m = Integer.parseInt(st.nextToken()); // 웍의 수
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < m; i++) {
			woks[Integer.parseInt(st.nextToken())]++; // 웍 개수 증가
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= i/2; j++) {
				if ((j == i - j && woks[j] >= 2)) { // 크기가 같은 웍 두개를 사용할 수 있는 경우
					dp[i] = 1;
				} else if (j != i - j && woks[j] > 0 && woks[i - j] > 0) { // 크기가 다른 웍 두개를 사용할 수 있는 경우
					dp[i] = 1;
				} else if (dp[j] != MAX && dp[i - j] != MAX) {
					dp[i] = Math.min(dp[i], dp[j] + dp[i - j]);
				}
			}
			//System.out.printf("dp[%d] : %d\n" ,i,dp[i]);
		}
		dp[n] = (dp[n] >= MAX ? -1 : dp[n]);
		System.out.println(dp[n]);
	}
}

 

이전에 쓰였던 부분문제로 더 큰 문제를 해결할 수 있을 것 같은 문제에는 dp를 떠올릴 수 있어야 한다.

dp를 떠올렸다면, dp[i] 가 가리키는 값을 어떤 변수로 둬야할지를 잘 설정해야 한다.

이 문제에서는, 최소 몇 번의 요리로 N개의 짜장면의 수를 처리할 수 있느냐가 관건이므로,

i는 1~N까지의 짜장면 개수, dp[i] 는 해당 i개의 짜장면을 만들기 위한 최소 요리 개수로 설정한다.

 

** dp[i] = i개의 짜장면을 만들기 위한 최소 요리 개수

 

주의해야할 조건은 다음과 같다.

1. 동시에 최대 두 개의 웍을 사용할 수 있다.
2. 만드려는 짜장면 개수 이상 크기의 웍을 사용하지 않는다.
3. ★★★ 크기가 같은 웍은 동시에 존재할 수 있다!!!! 

 

dp[] 는 MAX값으로 초기화하되, 0개의 짜장면을 만드는 개수는 0개로 초기화한다.

또한 웍을 입력받으며, 크기가 1~10000개의 웍 개수를 저장하는 wok[] 배열에 개수를 증가시킨다.

 

dp[i] 를 갱신하기 위해 for문을 i= (1~n)까지 돈다. 

이때, 두번째 이중 for문을 사용해서 j = (1~i//2) 까지 돈다.

• i//2 까지 탐색하는 이유는, dp[i] = dp[j]+dp[i-j] 이므로 j, i-j는 짝을 이루는 값이라 i/2까지만 탐색해도 결과는 같다.

이는 이전에 이미 구해놓은 dp[j]값으로 dp[i]를 구하기 위함이다.

즉, dp[6]을 구하기 위해서는 dp[1]+dp[5] , dp[2]+dp[4], dp[3]+dp[3] 을 통해 탐색할 수 있다.

 

이때, 만약 dp[3]+dp[3] 과 같이 j == i-j 일때, 3크기의 웍이 2개 이상 존재한다면, dp[3] = 1이지만, dp[6] = 1일 것이다. 

즉, 크기가 같은 웍을 두 개 사용한다면, 해당 웍이 2개이상 존재한지 확인하는 코드가 필요하다.

그 코드는 다음과 같다.

if ((j == i - j && woks[j] >= 2)) { // 크기가 같은 웍 두개를 사용할 수 있는 경우
	dp[i] = 1;
}

 

만약, j==i-j는 아니지만, j과 i-j크기의 서로 다른 크기의 웍이 존재한다면, 해당 요리 또한 1번으로 만들 수 있게 된다.

else if (j != i - j && woks[j] > 0 && woks[i - j] > 0) { // 크기가 다른 웍 두개를 사용할 수 있는 경우
	dp[i] = 1;
}

 

마지막으로 j, i-j 모두가 웍에 존재하는 경우가 아니라면, 기존의 dp값을 이용해서 갱신할 수 있다.

 else if (dp[j] != MAX && dp[i - j] != MAX) {
	dp[i] = Math.min(dp[i], dp[j] + dp[i - j]);
}

 

 

이렇게 n까지 dp[n]을 갱신한다면, 정답을 바로 출력할 수 있다.

아래의 람다식의 경우, dp[n]을 기존의 dp[]값으로 갱신할 수 없었을 때(웍들을 이용해서 n크기의 짜장면을 만들 수 없는 경우) dp[n]값이 MAX 초기값으로 남아있을 경우이다.

따라서 해당 경우, -1로 출력해줘야 한다. 

dp[n] = (dp[n] >= MAX ? -1 : dp[n]);
System.out.println(dp[n]);