이진 탐색

백준 1654번을 자바를 이용해 풀어보았다.
문제 링크 첨부한다.
https://www.acmicpc.net/problem/1654

Upper Bound

이진 탐색을 이용해서 앞서 풀었던 문제는 중복을 고려하지 않고 유일한 경우를 타겟팅해서 찾는 경우였다. 이번 문제는 중복이 존재하기 때문에 그 중에서도 가장 큰 값을 찾아내야 하는 문제를 해결해야 한다.

이를 해결하기 위해 하한선과 상한선 개념을 도입해야 한다.

1 2 3 3 3 4 6 과 같이 나열되어 있다고 가정하자. 오늘 문제는 이 배열 안의 여러 3 중 가장 우측에 있는 3을 찾기 원하는 것이다.

코드로 표현하면 다음과 같다.

while(l<=r){
	mid = (l+r)/2;

	int total = 0;
	for(int i=0; i<K; i++){
		total += mine[i]/mid;
	}

	if(total<N){
		r = mid - 1;
	}
	else{
		l = mid + 1;
	}
}

return r;

위 과정을 거치고 mid가 아닌 r을 반환해야 가장 마지막에 있는 3을 찾을 수 있다. 왜냐하면 while 문의 조건을 탈출할 때는 l이 가장 마지막 3보다 한 칸 더 뒤로 나가있을 것이기 때문이다.
나는 여기서 계속 mid 값을 반환하며 맞왜틀을 시전했다. ㅠ

다음은 제출한 코드다.

import java.util.*;

public class boj1654{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int K = sc.nextInt();
        int N = sc.nextInt();

        long[] mine = new long[K];
        for(int i=0; i<K; i++)
            mine[i] = sc.nextInt();

        Arrays.sort(mine);
        long l = 1, r = mine[K-1];
        long mid = 0;

        while(l<=r){
            mid = (l+r)/2;

            int total = 0;
            for(int i=0; i<K; i++){
                total += mine[i]/mid;
            }

            if(total<N){
                r = mid - 1;
            }
            else{
                l = mid + 1;
            }
        }

        System.out.println(r); // Upper Bound !!
    }
}

단순히 이진 탐색 기초 개념만 알고 있으면 무언가 하나 부족해서 계속 틀리는 문제였다. 깊이 고민할 수 있는 능력....을 기르자.