[백준] 1477 : 휴게소 세우기 - JAVA

🙋🏻‍♀️이진탐색 사용!

엄청엄청 많이 헷갈렸고, 고민했던 문제다.

Troubleshooting

public class Main {
public static int[] now;
public static ArrayList restArea;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int L = Integer.parseInt(st.nextToken());
		now = new int[N+2];
		restArea = new ArrayList<Integer>();
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++) {
			now[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(now);
		now[0] = 0;
		now[N+1] = L;
		for(int i=0; i<N+2; i++) {
			System.out.println(now[i]);
		}
		for(int i=1; i<N+2; i++) {
			int rest = now[i] - now[i-1] -1;
			restArea.add(rest);
		}
		for(int j=0; j<M; j++) {
			int max = (int)Collections.max(restArea);
			int start = 1;
			int end = max;
			Collections.sort(restArea);
			int middle = (start + end) /2;
			restArea.remove(Integer.valueOf(max));
			restArea.add(end-middle);
			restArea.add(middle-start);
		}
		System.out.println((int)Collections.max(restArea));
	}
}

문제

정상이라면 '0 200 701 800 1000'이 들어가야하는데, index 1에 값이 제대로 안들어가고 하나씩 밀려들어갔다. 그래서 마지막값도 1000으로 덮어써졌다.

원인

양 끝값 제외한 값들을 먼저 넣고, 정렬을 수행한게 문제였다.
양 끝은 여전히 0인데, 정렬하니 맨 뒷값이 앞으로 오게되기때문에 오류가 발생했다.

해결

now[0] = 0;
now[N+1] = L;
st = new StringTokenizer(br.readLine());
for(int i=1; i<=N; i++) {
	now[i] = Integer.parseInt(st.nextToken());
}

now배열의 처음과 끝에 값을 먼저 넣고, 나머지 값들을 채우는 걸 이후에 진행하니 해결됐다.

Troubleshooting 2

계속 다른 답이 나오고, 손으로 증명해봐도 답이 다르게나와서 코드 문제가 아님을 알았다.

매번 주유소 사이 거리의 최댓값을 구해서 절반으로 나누고 이 과정을 반복하면 최댓값의 최솟값이 보장되지 않는다.

기존 구간을 3개로 나누는데, 이 방법을 진행한다면

이런식으로 나누어지기 때문이다.

이는 기존 구간이 짝수개로 나누어질때에도 마찬가지다.
2의 배수개로 나누어지면 정답로직으로 나눌때와 최댓값의 최솟값이 동일하지만, 그게 아닌 짝수개로 나누어지는 경우에는 위 사진의 케이스와 동일하기 떄문이다.

따라서 주유소 사이 가능한 거리를 기준으로 개수를 카운트하며 이분탐색을 진행해야한다!

Troubleshooting 3

public class Main {
public static int[] now;
static int N;
static int M;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		int L = Integer.parseInt(st.nextToken());
		now = new int[N+2];
		now[0] = 0;
		now[N+1] = L;
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++) {
			now[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(now);
		binarySearch(1,L-1);
	}
	
	public static void binarySearch(int start, int end) {
		while(start <= end) {
			int count = 0; 
			int middle = (start + end) /2;
			for(int i=N+1; i>0; i--) {
				int dis = now[i] - now[i-1] -1;
				count += dis/middle;
			}
			if(count>M) start = middle +1;
			if(count<M) end = middle -1;
		}
		System.out.println(start);
	}
}

문제

예제를 입력하면 콘솔에 결과가 안찍힌다.

원인

디버깅해보니

71거리로 주유소를 세운다고 가정했을 때, 7개가 들어가는데 이렇게 'count == M' 일때는 start, end를 변경해주는 코드가 없어서 while문을 빠져나오지 못한다.

해결

최댓값의 최솟값을 구하는것이기때문에, count == M인 middle이 정답이 될 경우에도 middle이 더 작을 수 있는지 체크해야한다.
따라서 count == M인 경우에는 end = middle -1 을 헤야한다.

---

제출코드

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

public class Main {
public static int[] now;
static int N;
static int M;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		int L = Integer.parseInt(st.nextToken());
		now = new int[N+2];
		now[0] = 0;
		now[N+1] = L;
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++) {
			now[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(now);
		binarySearch(1,L-1);
	}
	
	public static void binarySearch(int start, int end) {
		while(start <= end) {
			int count = 0; 
			int middle = (start + end) /2;
			for(int i=N+1; i>0; i--) {
				int dis = now[i] - now[i-1] -1;
				count += dis/middle;
			}
			if(count>M) start = middle +1;
			if(count<=M) end = middle -1;
		}
		System.out.println(start);
	}
}

---

다른풀이

이 풀이는 어디에서 본 풀이가 아니라, 토론후에 얻은 풀이다.

기존 휴게소 사이의 거리를 저장한 배열을 A라고 하자.
휴게소 사이의 거리를 없데이트 할 배열을 B라고 하자.
A 배열은 수정하지않고, B 배열만 수정한다.
처음에는, A와 동일한 내용을 B에 넣는다.
B의 최댓값을 구하고, 이것에 해당하는 A배열데이터를 /n 해준다.
n은 해당 데이터를 처음 나누면 2, 또 나누면 3, 또 나누면 4 .. 이렇게 증가하기때문에 각 데이터마다 몇 번 나누었는지 체크하는 배열을 하나 더 만들어야한다.
나눠지는 거리의 크기가 달라도, 나눠지는 거리의 최대값만 저장해주면 된다.
이렇게 총 M번 반복한 후 B배열의 최댓값을 출력하면 정답이다.

시간복잡도는 O(M) = O(100), 공간복잡도는 N크기의 배열 3개를 사용하는데 N의 최대가 50이므로 150이고, int타입이므로 150*4byte = 600byte 이다.
따라서 이 로직을 사용해도 계산이 가능할 것 같다.

하지만, 이진탐색이 훨씬 빠르다!

---

참고
https://moonsbeen.tistory.com/273
https://gusdnr69.tistory.com/277