[Gold V] 개업 - 13910 (Java)
분류
다이나믹 프로그래밍
문제 설명
해빈이는 짜장면을 정말 좋아한다. 짜장면을 너무 좋아한 나머지 짜장면만 파는 중국집을 개업했다! 해빈이는 양손잡이여서 동시에 두 개의 웍(중국 냄비)을 사용하여 요리할 수 있다. 그러나 해빈이는 낭비를 매우 싫어하기 때문에 요리 할 때, 필요 이상 크기의 웍을 사용하지 않으며, 주문 받은 짜장면의 그릇 수에 딱 맞게 요리한다.
<웍>
예를 들어 짜장면 4그릇을 주문 받았는데 5그릇 이상을 요리하지 않으며, 4그릇을 요리할 수 있는 웍에 3그릇 이하의 요리를 하지 않는다.
해빈이가 5그릇을 주문 받았고, 해빈이가 가지고 있는 웍의 종류가 1, 3그릇 용이라면 처음에 1,3그릇용 웍을 동시에 이용하여 4그릇을 만들고 다음 1그릇용 웍을 이용하여 1그릇을 만들어 총 5그릇을 두 번의 요리로 만들 수 있다.
해빈이가 주문 받은 짜장면의 수와 가지고 있는 웍의 크기가 주어질 때, 최소 몇 번의 요리로 모든 주문을 처리할 수 있는지 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 해빈이가 주문 받은 짜장면의 수N(1≤N≤10,000)과 가지고 있는 웍의 개수 M(1≤M≤100)이 주어진다. 두 번째 줄에는 웍의 크기 Si(1≤Si≤N)이 M개가 주어지며 같은 크기의 웍을 여러 개 가지고 있을 수 있다.
출력
해빈이가 모든 주문을 처리하기 위해 해야 하는 최소 요리 횟수를 출력한다. 만약 모든 주문을 처리 할 수 없는 경우 -1을 출력한다.
풀이 (동적 프로그래밍)
시간 복잡도 O(n^3) 공간 복잡도 O(n)
아이디어: dp[n] 테이블을 n개의 주문을 최소한으로 해치우는 가짓수를 저장, 웍은 최대 2종류만 사용 가능하다는 점을 이용
dp[i] = dp[i-work]+1 의 관계식을 이용 (work는 한번에 웍을 돌릴 때 만들 수 있는 요리의 갯수)
우리는 웍을 개별로 사용한 경우와 두 개의 웍을 같이 사용한 경우를 체크하여서 경우를 체크해야한다.
import java.io.*;
import java.util.*;
public class Main {
public static int sti(StringTokenizer st){
return Integer.parseInt(st.nextToken());
}
public static long stl(StringTokenizer st){
return Long.parseLong(st.nextToken());
}
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 k = Integer.parseInt(st.nextToken());
long[] dp = new long[10001];
Arrays.fill(dp,1000000);
dp[0] = 0;
int[] array = new int[k];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < k; i++) {
array[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < k; i++) {
int op1 = array[i];
for (int j = i+1; j < k; j++) {
int op2 = array[j];
for (int l = 1; l <= n; l++) {
int sum = op1+op2;
if(l-op1>=0) dp[l] = Math.min(dp[l],dp[l-op1]+1);
if(l-op2>=0) dp[l] = Math.min(dp[l],dp[l-op2]+1);
if(l-sum>=0) dp[l] = Math.min(dp[l],dp[l-sum]+1);
}
}
}
if (dp[n]>=1000000) {
System.out.println(-1);
} else {
System.out.println(dp[n]);
}
}
}if(l-op1>=0) dp[l] = Math.min(dp[l],dp[l-op1]+1);
if(l-sum>=0) dp[l] = Math.min(dp[l],dp[l-sum]+1);위에 방식으로 사용하지 않는 이유는
웍의 크기가 [2, 3]이고 주문된 짜장면의 양이 7이라고 가정할 때
위에 방식의 경우, 왹의 합은 2+2, 2+3, 3+3 의 경우만 체크하여 4,5,6 7을 만들기 위한 방법을 구할 수 없는 반면
첫 뻔재 코드의 방식의 경우 웍의 모든 가능한 조합을 고려 할 수 있기 때문이다.
풀이 (동적 프로그래밍)
시간 복잡도 O(n^2) 공간 복잡도 O(n)
아이디어: dp[n] 테이블을 n개의 주문을 최소한으로 해치우는 가짓수를 저장, 웍은 최대 2종류만 사용 가능하다는 점을 이용
미리 웍의 조합을 사용하여 음식을 만드는 경우를 저장하고 저장된 공간을 통해 최신화
j <= i/2로 설정하는 이유는, j와 i-j가 바뀐 경우는 이미 계산되었기 때문 예를 들어, i가 6일 때, j가 2인 경우와 j가 4인 경우는 사실상 같은 경우이다. (2+4와 4+2는 같은 것으로 취급). 따라서 j를 i/2까지만 반복해도 모든 경우를 고려할 수 있다.
import java.io.*;
import java.util.*;
public class Main {
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 M = Integer.parseInt(st.nextToken());
int[] dp = new int[N+1];
int[] arr = new int[M];
Arrays.fill(dp, 1_000_000); // dp 배열을 최대 값으로 초기화한다.
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
// 동적 프로그래밍을 수행한다.
for (int i = 0; i < M; i++) {
for (int j = i + 1; j < M; j++) {
if (arr[i] + arr[j] <= N) {
dp[arr[i] + arr[j]] = 1;
}
}
dp[arr[i]] = 1;
}
for (int i = 2; i <= N; i++) {
for (int j = 0; j <= i / 2; j++) {
dp[i] = Math.min(dp[i], dp[j] + dp[i-j]);
}
}
// 모든 주문을 처리할 수 없는 경우 -1을 출력한다.
if (dp[N] >= 1_000_000) {
System.out.println(-1);
} else {
System.out.println(dp[N]);
}
}
}