[백준 22953] 도도의 음식 준비 - Java 문제풀이

문제 링크: https://www.acmicpc.net/problem/22953

 

문제

도도는 주방장이다. 총 K개의 요리가 준비되는 최소 시간을 구해야 한다.

각각의 요리사는 자신만의 음식 조리 시간이 있다. 음식 조리 시간은 음식 하나를 만들 때 걸리는 시간이다.

도도는 요리사에게 격려를 해줄 수 있다. 격려받은 요리사는 영구적으로 음식 조리 시간이 1초 감소한다.

도도는 한 요리사에게 여러 번 격려할 수 있고, 요리사의 음식 조리 시간을 1초 미만으로 줄일 수는 없다.

도도를 위해 요리에 걸리는 최소 시간을 출력하는 프로그램을 만들어 보자.

 

입력

첫째 줄에 요리사의 수 N (1 ≤ N ≤ 10), 만들어야 할 음식의 개수 K (1 ≤ K ≤ 1000000), 격려해줄 수 있는 횟수 C (1 ≤ C ≤ 5)가 주어진다.

둘째 줄에 길이가 N인 정수 수열 A가 주어진다. i로 주어지는 수 Ai는 i번째 요리사의 음식 조리 시간이다. (1 ≤ C ≤ N, 1 ≤ Ai ≤ 1000000 )

 

출력

첫째 줄에 K개의 음식 조리가 완료되는 최소 시간을 출력한다.

풀이

접근법

1. 어떤 요리사를 격려할 지는 완탐으로 결정하자 !
2. 시간을 모두 돌기에는 범위가 너무 크니까, 시간을 이진탐색으로 구하자

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static int N, K, C;
    private static long ans;
    private static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N=Integer.parseInt(st.nextToken());
        K=Integer.parseInt(st.nextToken());
        C=Integer.parseInt(st.nextToken());
        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++) arr[i] = Integer.parseInt(st.nextToken());
        ans = -1;
        recur(0, C);
        System.out.println(ans);
    }

    private static long getCount(long mid) {
        long count =0 ;
        for(int i=0;i<N;i++) count += mid/arr[i];
        return count;
    }
    
    // 1. 어떤 요리사를 격려할 지는 완탐으로 결정하자 !
    private static void recur(int cur, int remainC) {
        if (cur == N || remainC == 0) {
            long s = 0L;
            long e = 1000000000000L;
            while(s<=e) {
                // 2. 시간을 모두 돌기에는 범위가 너무 크니까, 시간을 이진탐색으로 구하자
                long mid = (s+e)/2;
                long num = getCount(mid);
                if (num >= K) {
                    ans = ans == -1 ? mid : Math.min(ans, mid);
                    e = mid-1;
                } else {
                    s = mid+1;
                }
            }
            return;
        }

        // 현재 요리사를 줄이는 경우
        if (arr[cur] > 1) {
            arr[cur]--;
            recur(cur, remainC-1);
            arr[cur]++;
        }
        // 현재 요리사를 줄이지 않는 경우
        recur(cur+1, remainC);
    }
}

 

20분 걸렸다