[백준] 3090 차이를 최소로 [자바]

 

---

https://justicehui.github.io/coci/2019/01/13/BOJ3090/

백준3090 차이를 최소로

https://ghdic.github.io/ps/boj-3090/

백준 3090 차이를 최소로 풀이

https://www.acmicpc.net/board/view/32602

글 읽기 - 이분탐색에 대해 잘 아시는분 계신가요??

 

---

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

public class Main {
	static int N,T;
	static int[] arr;
	static int[] result;
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 		N = Integer.parseInt(st.nextToken());
 		T = Integer.parseInt(st.nextToken());
 		arr = new int[N];
 		result = new int[N];
 		int max = 0;
 		st = new StringTokenizer(br.readLine(), " ");
 		for(int i = 0; i < N; i++) {
 			int a = Integer.parseInt(st.nextToken());
 			arr[i] = a;
 		}
 		for(int i = 0; i < N-1; i++) {
 			int su = Math.abs(arr[i]-arr[i+1]);
 			max = Math.max(max, su);
 		}
 		int left = 0;
 		int right = max+1;
 		int [] temp = new int[N];
 		while(left != right) {
 			int mid = (left + right) / 2;
 			if(isPossible(mid)) {
 				right = mid;
 			}
 			else {
 				left = mid+1;
 			}
 		}
 		StringBuilder sb = new StringBuilder();
 		for(int i = 0; i < N; i++) {
 			sb.append(result[i]).append(' ');
 		}
 		System.out.println(sb);
 	}
 	static boolean isPossible(int n) {
 		//양방향으로 되는지 계산
 		int[] carr = new int[N];
 		long cnt = 0; // 더하는 과정에서 int범위를 초과할 수 있음
 		copy(carr);
 		for(int i = 0; i < N-1; i++) {
 			//-> 앞쪽의 배열은 바뀌면 안된다.
 			//같은 경우 따로 연산이 필요없음 클 경우 (4 2) 큰 수를 빼야하는데 앞쪽의 배열은 바뀌면 안됨
 			if(carr[i] + n < carr[i+1]) { //(앞쪽 배열이 작음) mid를 더한 값이 다음 배열보다 작으면 앞쪽배열에 mid를 더한 값으로 변경해줌 이 때 연산횟수는 기존 배열 - 바뀐 값 이다. 
 				cnt += carr[i+1] - (carr[i] + n);
 				carr[i+1] = carr[i] + n;
 			}
 		}
 		
 		for(int i = N-1; i > 0; i--) {
 			//<- 뒤쪽의 배열은 바뀌면 안된다. 
 			if(carr[i]+n < carr[i-1]) {//(뒤쪽 배열이 작음) (4 2) 뒤쪽의 배열은 바뀌면 안됨
 				cnt += carr[i-1] - (carr[i] + n);
 				carr[i-1] = carr[i] + n;
 			}
 		}
 		if(cnt > T) {
 			return false; //연산이 많다면 mid를 증가시켜준다.
 		}
 		else { //연산의 수가 <= T가 될 때까지 돌림 예제2 (4 2 3 7 6) n=2 - > 4 2 4 6 4 = 4번의 연산
 			for(int i = 0; i < N; i++) {
 				result[i] = carr[i];
 			}
 			return true;
 		}
 	}
 	static void copy(int[] arrtmp) {
 		for(int i = 0; i < N; i++) {
 			arrtmp[i] = arr[i];
 		}
 	}
}