[백준] 13910 개업 (JAVA)

문제 풀러가기

문제

난이도: 골드 5

문제 설명
해빈이는 짜장면을 정말 좋아한다. 짜장면을 너무 좋아한 나머지 짜장면만 파는 중국집을 개업했다! 해빈이는 양손잡이여서 동시에 두 개의 웍(중국 냄비)을 사용하여 요리할 수 있다. 그러나 해빈이는 낭비를 매우 싫어하기 때문에 요리 할 때, 필요 이상 크기의 웍을 사용하지 않으며, 주문 받은 짜장면의 그릇 수에 딱 맞게 요리한다.

예를 들어 짜장면 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을 출력한다.

---

문제 분석

진짜 오랜만에 푸는 알고리즘..

문제 분류는 DP로 되어있는데, bfs를 사용해 완탐으로 풀어봤다

웍의 최대 개수가 100, 손이 두 개인 한정적인 조건으로 생각하면
완탐으로도 충분히 가능한 문제

내 코드

package day_240401;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_Main_13910_개업 {
	
	static class Data {
		int left, right, cnt, make;
		public Data(int left, int right, int cnt, int make) {
			this.left = left;
			this.right = right;
			this.cnt = cnt; //횟수
			this.make = make;
		}
	}

	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()); //짜장면의 수
		int M = Integer.parseInt(st.nextToken()); //웍의 수
		
		int[] woks = new int[M+1];
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i<M; i++) {
			woks[i] = Integer.parseInt(st.nextToken());
		}
		//입력 완료
		
		int[] dist = new int[10002];
		boolean[] visit = new boolean[10002];
		
		Queue<Data> q = new ArrayDeque<>();
		q.offer(new Data(0,0,0,0));

		//bfs 시작
		while(!q.isEmpty()) {
			Data cur = q.poll();
			//System.out.println("left " + cur.left + " right " + cur.right + " cnt " + cur.cnt + " make " + cur.make);
			//주문 받은 짜장면 완성
			if(cur.make == N) {
				break;
			}
			
			for(int i = 0; i<M+1; i++) {
				for(int j = 0; j<M+1; j++) {
					if(i==j) continue;
					//if(cur.make+woks[i]+woks[j]>=10001) continue;
					
					if(cur.make+woks[i]+woks[j]<=10001 && !visit[cur.make+woks[i]+woks[j]]) {
						q.offer(new Data(woks[i], woks[j], cur.cnt+1, cur.make+woks[i]+woks[j]));
						visit[cur.make+woks[i]+woks[j]] = true;
						dist[cur.make+woks[i]+woks[j]] = cur.cnt+1;
					}
				}
			}
		}
		
		if(dist[N] == 0) System.out.println(-1);
		else System.out.println(dist[N]);
		//System.out.println(Arrays.toString(dist));
		
	}
	
	

}