boj 2512

상한가를 구하는 문제

처음에는 이해가 잘 안됬다..
그래서 반 나누고 반모두 정한거에 m을 빼서 반 개수로 나누는 문제인줄...

그게 아니여서 찾아 보았다.

파라메트릭 서치

최적화 문제(특정 변수의 최솟값 최댓값을 구하는 문제) 를 결정 문제로 바꾸어 푸는거

최적화 문제

• 소주를 좋아하는 나이가 가장 어린사람

결정 문제

• 너 소주 좋아하니 : 네 , 아니오

누구에게 묻는것이 옳을까
처음은 아무 정보도 없으니 당연히 가운데 사람일것이다

이처럼 바이너리 서치와 매우 흡사한 문제이다

정답이 될수 있는 값인지 아닌값인지 쉽게 판단할 수 있어야 한다
또한 정답이 될수 있는 값들이 연속적이여야 한다

그럼 다시 문제에 들어와서

문제 풀이

120 110 140 150 에서 합치면 485가 나올수 있는 상한가를 구하는 것이다

그럼 우선 해당 Arr 에서 max 150 (최대로 나올수 있는 값) 0 (최소로 나올수 있는 값) 이 start end 가 될 것 이다

int start = arr[n-1];
int end = 0;

그 후 반복적으로
1. mid 구하기
2. 위 arr 에서 mid 크면 h 에 + mid 아니면 +arr[i] 를 한다
3. 만약 h 가 mid 보다 작거나 같으면 start = m+1
4. 크거면 end = m -1
5. end 가 답

전체 코드

private static int[] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

        arr = new int[n];
        st = new StringTokenizer(br.readLine());
        int end = 0;
        int start = 0;
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
            if(arr[i]>end){
                end = arr[i];
            }
        }
        int m = Integer.parseInt(br.readLine());
        int mid = 0;
        while(start <= end){
             mid = (start+end)/2;
            int b = 0;
            
            for(int i=0; i<n; i++){
                if(arr[i]>mid){ b += mid;}
                else{
                    b+=arr[i];
                }
            }
            if(b<=m){
                start = mid +1;
            }else{
                end = mid-1;
            }
        }
        System.out.println(end);

    }

---

처음 보는 유형이여서 좀 더 해당 유형을 봐야 알거 같다