백준 13902 - (Java)개업 2

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

13902번: 개업 2

1. 유형

다이내믹 프로그래밍

 

2. 문제 분석

 

사용한 자료구조

set <- 중복 없이 웍의 크기를 저장

 

- 조합을 사용해서 만들 수 있는 모든 웍의 크기를 구합니다.

예를 들어 1 2 3 크기의 웍이 주어졌으면, 1 2 3 4 5 크기의 웍을 만들 수 있습니다.

 

- 짜장면 1그릇부터 N그릇까지 만들 수 있는 최소의 웍 개수를 Dp에 저장해줍니다.

 

예를 들어, 위에서 구한 웍들을 사용해서 N그릇을 만들고 싶다면

 

dp [N-1] +1, dp [N-2] +1, dp [N-3]+1, dp [N-4]+1, dp [N-5]+1 중에서 가장 최솟값을 구해서

 

dp [N]에 대입해주면 됩니다. 

 

위 과정을 1~N까지 반복해주면 됩니다.

 

중간중간 인덱스 예외처리에 신경을 써주면 에러 없이 해결 가능합니다.

 

 

만들 수 있는 모든 웍의 크기를 재귀를 사용해서 구함.

 

위에서 설명한 점화식

 

 

3. 코드

 

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

public class Main {
	static Set<Integer> set;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		int N, M, a, b, INF = Integer.MAX_VALUE;
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		int arr[] = new int[M];
		st = new StringTokenizer(in.readLine());
		for(int i=0;i<M;i++) {
			arr[i] = stoi(st.nextToken());
		}
		int dp[] = new int[N + 1];
		set = new HashSet<>();
		for(int i=1; i<3; i++) {
			combine(i, arr, 0, 0, 0);
		}
		for(int x: set) {
			if(x<=N)
				dp[x] = 1;
		}
		for (int i = 0; i <= N; i++) {
			if(set.contains(i)) continue;
			int minval = INF; 
			for(int x: set) {
				if(i-x > 0 && dp[i-x]!=INF) {
					minval = Math.min(minval, dp[i-x]+1);
				}
			}
			dp[i] = minval;
		}
		if(dp[N]==INF)
			System.out.println(-1);
		else
			System.out.println(dp[N]);
	}
	static void combine(int len, int arr[], int arrIdx, int selNum, int sum) {
		if(len == selNum) {
			set.add(sum);
			return;
		}
		
		for(int i=arrIdx; i<arr.length; i++) {
			combine(len, arr, i+1, selNum+1, sum+arr[i]);
		}
	}

	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}