백준 휴먼 파이프라인(22981)

그리디 알고리즘 문제를 풀어보았다.

 

 

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

22981번: 휴먼 파이프라인

 

문제를 보면 A, B 두팀의 합산으로 이루어진 분당 처리량을 구하면 될거 같다.

 

• 한팀은의 분당 처리량은 주어진 처리량값중에 가장 작은 값이다.
• 그 다음 처리량 값을 구하면 해당 해 기준으로 인원수 처리를 하면 된다.

 

해서 구할수 있는 점화식이 있었다.

 

분당 처리량 = (최대인원 - 선택인덱스) * 선택인덱스 처리량  + (선택인덱스 * 최소 처리량) 

 

이 되겠다.

 

K는 long 타입으로 주의해야한다. 계속 numberFormatException이 나오길래 뭔가했었다.

 

 

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

public class Main {

    public static void main(String[] args) throws IOException {
        solution();
    }

    public static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        long K = Long.parseLong(st.nextToken());

        long[] works = new long[N];

        st = new StringTokenizer(br.readLine());
        for (int i=0 ; i < N; i++) {
            works[i] = Long.parseLong(st.nextToken());
        }

        Arrays.sort(works);

        long max = 0;

        for (int i=1; i < N; i++) {
            long num = ((N-i) * works[i]) + (i * works[0]);
            max = Math.max(max, num);
        }

        long answer = K / max + (K % max == 0 ? 0 : 1);

        System.out.println(answer);
        
    }
}

 

결과