boj13910 개업

링크

13910번: 개업

문제

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

<웍>

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

나의 풀이

• 2개씩 사용할 경우 나올 수 있는 경우의 수를 구하고, (웍으로 요리할수 있는 그릇의 개수를 담고 있는) 웍 배열에 추가한다.

  • 이때, 웍 배열은 오름차순으로 정렬한다.

• dp배열을 추가해서 order+1 크기로 생성하고, 이 안에는 각자의 경우마다 최소 cnt를 추가해주는 방식으로 풀었다.

• 문제 부분

  • 계속해서 51%에서 에러가 나서 이유를 찾을 수 없었는데 알고보니 -1 처리하는게 빠져있었다...

• 핵심 코드

  for (int i = 1; i <= order; i++) {
      for (int j = 0; j < wok.size(); j++) {
          if(i<wok.get(j)) break;
          else if(i==wok.get(j)){
              dp[i]=1;
              break;
          }else if(dp[i-wok.get(j)]!=Integer.MAX_VALUE){
              dp[i] = Math.min(dp[i],dp[i-wok.get(j)]+1);
          }
      }
  }

• 전체 코드

  package Baekjoon.java.silver;
  
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.*;
  import java.util.stream.Collectors;
  
  public class boj13910 {
      static int N, mywok[], order, answer, dp[];
      static List<Integer> wok = new ArrayList<>();
  
      public static void main(String[] args) throws Exception {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(br.readLine());
  
          answer = -1;
          order = Integer.parseInt(st.nextToken());
          N = Integer.parseInt(st.nextToken());
          mywok = new int[N];
          dp = new int[order + 1];
          Arrays.fill(dp,Integer.MAX_VALUE);
          dp[0] = 0;
          st = new StringTokenizer(br.readLine());
          for (int i = 0; i < N; i++) {
              mywok[i] = Integer.parseInt(st.nextToken());
              wok.add(mywok[i]);
          }
  
          for (int i = 0; i <N; i++) {
              for (int j = i+1; j < N; j++) {
                  if (mywok[i] + mywok[j] <= order) {
                      wok.add(mywok[i] + mywok[j]);
                  }
              }
  
          }
          wok = wok.stream().sorted().collect(Collectors.toList());
          cook();
          if(Integer.MAX_VALUE==dp[order])
              System.out.println(-1);
          else {
              System.out.println(dp[order]);
          }
      }
  
      public static void cook() {
          for (int i = 1; i <= order; i++) {
              for (int j = 0; j < wok.size(); j++) {
                  if(i<wok.get(j)) break;
                  else if(i==wok.get(j)){
                      dp[i]=1;
                      break;
                  }else if(dp[i-wok.get(j)]!=Integer.MAX_VALUE){
                      dp[i] = Math.min(dp[i],dp[i-wok.get(j)]+1);
                  }
              }
          }
      }
  }

결과