[SWEA] 3814 평등주의

출처: [SWEA] SW 문제해결 심화 - Ad Hoc Algorithms

Binary Search (이분 탐색) 

Binary Search (이분 탐색)

[탐색] Parametric Search 

[탐색] Parametric Search

 

숫자 X의 범위는  1 ≤ K ≤ 109이므로 인접한 두 수의 최소·최대는 다음과 같습니다.

    최소: 0  ← left

    최대: 109 - 1 ← right

▶ 인접한 두 수의 차이를 기준(mid)으로 최적의 연산횟수를 찾아갑니다.  

 

시뮬레이션

: 두 수의 차이를 기준값(mid)으로 맞추기 위한 연산횟수 확인

[인접한 두 수의 차이 = 『2』 (=mid)로 가정]

① 오른쪽 방향으로 copyArr[i+1] - copyArr[i]를 계산합니다.

② 차이가 기준(mid)보다 크면 연산처리하여 우측의 수를 감소시킵니다.

③ 이때, 최대 연산 횟수(K)보다 더 많은 연산처리가 필요하면 기준(mid)을 작게 설정.(right = mid)

▶ 중간에 copyArr[4] = 7을 두번 연산하여 5로 감소

④ 오른쪽 방향의 탐색이 정상적으로 끝난 상태에서, 왼쪽방향으로 동일한 작업을 해줍니다.

▶ 왼쪽 방향으로 탐색 시, copyArr[i-1] - copyArr[i] ≥ mid 이므로 연산이 적용되지 않습니다.

양쪽 탐색이 정상적으로 끝났다면 현재 기준(mid)을 주어진 연산 횟수 내에서 만족하는 것을 의미합니다.

 

⑤ 최적화된 인접한 두 수의 차이를 찾기위해 left ≥ right 될때까지 작업 반복합니다.

* 실제 위의 예시 배열은 인접한 두 수의 차이를 주어진 연산 횟수 내에서 『1』까지 할 수 있습니다.

※ 양쪽으로 차이를 비교하기 때문에 인접한 두 수의 차이를 절대값으로 기준(mid)과 비교하지 않습니다.

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
    static int N, K, answer;
    static int[] arr, copyArr;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
 
            arr = new int[N + 1];
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
            parametricSearch();
            // 정답 출력
            System.out.println("#" + tc + " " + answer);
        }
    }
 
    private static void parametricSearch() {
        int left = 0;
        int right = 1000000000;
        while (left < right) {
            int mid = (left + right) >> 1;
 
            if (!isPossible(mid)) {
                left = mid + 1;
                answer = left;
            } else {
                right = mid;
            }
        }
    }
     
    private static boolean isPossible(int mid) {
        copyArr = arr.clone();
        int oprCnt = 0;
         
        // 첫번째 원소부터 마지막 원소까지 인접한 두 수 차이(gap)에 따른 처리 (오른쪽 방향)
        for (int i=1; i<N; i++) {
            int gap = copyArr[i+1] - copyArr[i];
            // 인접한 두 수의 차이가 mid이상이면
            if (gap >= mid) {
                // 연산 사용 횟수 누적
                oprCnt += (gap - mid);
                // 연산된 만큼 우측의 수를 감소시켜줍니다.
                copyArr[i+1] -= (gap - mid); 
                // 최대 연산 횟수를 초과 했는지 확인
                if(oprCnt > K) return false;
            }
        }
         
        // 마지막 원소부터 첫번째 원소까지 인접한 두 수 차이(gap)에 따른 처리 (왼쪽 방향)
        for (int i=N; i>1; i--) { 
            int gap = copyArr[i-1] - copyArr[i];
            // 인접한 두 수의 차이가 mid이상이면
            if (gap >= mid) {
                // 연산 사용 횟수 누적
                oprCnt += (gap - mid);
                // 연산된 만큼 좌측의 수를 감소시켜줍니다.
                copyArr[i-1] -= (gap - mid); 
                // 최대 연산 횟수를 초과 했는지 확인
                if(oprCnt > K) return false;
            }
        }
        return true;
    }
}