SW Expert 16081 JAVA : 식신

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

 

풀이 예상

K의 범위가 너무 커서 일반적인 방법으로는 절대 안되겠다고 생각이 들었다. 

그래서 K를 이분탐색을 통해 줄여가면서 최솟값을 찾아내는 풀이 방법을 생각했다.

 

풀이방법 (접근 방법 & 시간복잡도)

1. 사람들의 능력치를 내림차순으로 정렬하고, 음식 난이도를 오름차순으로 정렬한다.

2. start = 0, end = 곱해서 최대가 나오는 수 로 설정하고 이분탐색을 시작한다.

3. mid값이 최소가 되기 위한 트레이닝 횟수를 count 한다.

4. count가 K보다 크다면 mid가 최솟값이 되기위해 트레이닝 횟수가 더 필요하다는 뜻이므로 최솟값(mid)을 증가시켜야 하므로 start값을 mid+1로 갱신해준다.

5. 아닌경우 end값을 mid-1로 갱신

 

ex) 예제 입력, N = 3, K = 5 , people[] = {4,2,1}, food[] = {2,3,1}

3 5
4 2 1
2 3 1

 

people[] = {4, 2, 1}, food[] = {1, 2, 3}, 곱한값의 최솟값(mid) 가 3인경우를 계산해보면

i = 0 일 때

(4 - ?) x 1 이 3이하가 되려면 ? 는 1 이상이여야 한다. => count = 1

i = 1 일 때

(2 - ?) x 2 이 3이하가 되려면 ? 는 1 이상이여야 한다. => count = 2

i = 1 일 때

(1 - ?) x 3 이 3이하가 되려면 ? 는 0 이상이여야 한다. => count = 2

 

 => mid = 3인 경우 count(2) < K(5) 이므로 최솟값을 내려도 된다. => end값이 갱신된다.

 

mid가 2인경우

i = 0 일 때

(4 - ?) x 1 이 2이하가 되려면 ? 는 2 이상이여야 한다. => count = 2

i = 1 일 때

(2 - ?) x 2 이 2이하가 되려면 ? 는 1 이상이여야 한다. => count = 3

i = 1 일 때

(1 - ?) x 3 이 2이하가 되려면 ? 는 1 이상이여야 한다. => count = 4

 

=> mid = 2인 경우 count(4) < K(5) 이므로 최솟값을 내려도 된다. => end값이 갱신된다.

 

이와 같은 과정은 다음과 같은 코드로 나타낼 수 있고 , 반복한다면 start값이 팀 점수의 최솟값이다. 

for (int i = 0; i < N; i++) {
	count += Math.max(people[i] - mid / food[i],0); //최대가 0 인 이유는 음수가 나올 경우를 제거해주기 때문
}

 

 

 

시간복잡도 => O(N* log K)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Solution {
    static int N;
    static long K;
    static long[] food;
    static Long [] people;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        for (int t = 1; t <= T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            K = Long.parseLong(st.nextToken());
            people = new Long[N];
            food = new long[N];
 
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                people[i] = Long.parseLong(st.nextToken());
            }
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                food[i] = Long.parseLong(st.nextToken());
            }
 
            Arrays.sort(food); //오름차순
            Arrays.sort(people, Collections.reverseOrder()); //내림차순
 
            long start = 0;
            long end = food[N-1] * people[0];
 
            while(start <= end) {
                long mid = (start+end)/2;
                long count = 0;
 
                for (int i = 0; i < N; i++) {
                    count += Math.max(people[i] - mid / food[i],0);
                }
 
                if(count <= K) {
                    end = mid -1;
                }else {
                    start = mid+1;
                }
 
            }
 
            sb.append("#").append(t).append(" ").append(start).append("\n");
        }
 
        System.out.println(sb);
 
 
    }
}

결과