백준 1477 - 휴게소 세우기

문제 링크 : https://www.acmicpc.net/problem/1477

 

풀이 과정

처음 접근 방법은, 최대 길이 구간의 중간에 휴게소를 설치하는 아이디어였다.

 

예를 들면, n = 4, l = 700 이고

휴게소 위치 :  100  200  500  600
구간 길이 :  100  100  300  100  100

일 때,

최대 길이 구간인 200 ~ 500 중간에 휴게소를 설치하여

휴게소 위치 :  100  200 (350) 500  600
구간 길이 :  100  100  150  150  100  100

 

다음과 같이 최대 길이 구간을 찾고, 그 구간을 분할하는 걸 m번 반복할 생각이였다.

 

하지만 이 아이디어는 최적의 방법이 아니다.

 

중간 설치 아이디어 문제점 : 균일하게 나누는 것이 더 최적이다.

예를 들면, n = 2, l = 700 이고

휴게소 위치 :  100  600
구간 길이 :  100  500  100

일 때,

 

중간 설치 아이디어로 휴게소를 2개 설치하면 다음과 같다.

휴게소 위치 :  100 (350)  600
구간 길이 :  100  250  250  100

 

휴게소 위치 :  100  (225)  (350)  600
구간 길이 :  100  125   125  250   100

 

이렇게 나누면, 휴게소를 2개 설치해 구간을 두 번 나누었음에도 최대 길이 구간은 250이다. 하지만 균일하게 나누면 어떨까?

 

휴게소 위치 :  100  (266)  (433)  600
구간 길이 :  100  166   167  167   100

 

최대 길이 구간이 167이다. 이를 통해 한 구간 안에서는 휴게소 개수 + 1 만큼 구간을 균일하게 나누는 것이 최적임을 알 수 있다. 최대 길이 구간을 발견하면, 그 구간 안에서 휴게소의 개수만큼 균일하게 세부 구간으로 나누어져야 한다.

 

n이 0이면, 다음과 같이 정답을 출력할 수 있다. 완전히 나누어지지 않을 수도 있기에 나머지 처리가 중요하다.

System.out.println((l / (m + 1)) + ((l % (m + 1) != 0) ? 1 : 0));

 

 

그런데, 한 구간 안에 휴게소가 몇 개 필요한지는 어떻게 구할 수 있을까? 한 구간 안에 휴게소를 이미 여러 개 설치한 후에, 몇 번의 연산을 거쳐 다시 이 구간이 최대 길이 구간이 되었다면, 이 구간에 또 휴게소를 설치해서 분할해야 하는데, 어떻게 처리해야 할까?

 

휴게소를 진짜 설치하지는 않는다

우리는 처음에 휴게소를 설치하지 않은 상태에서 시작해서, 특정 구간에 한 개씩 휴게소를 설치해보면서 최대 길이 구간을 줄여나가야 한다. 

 

입력으로 주어진 휴게소들은 고정되어 위치가 변하지 않으므로 한 고정된 구간으로 본다. 이 때 새로 설치하는 휴게소들도 아예 고정해버리면 (배열에 기록) 균일하게 나눠야 할 때 번거롭게 수정해야 할 수도 있다.

 

특정 구간에 휴게소를 몇 개 설치했는지를 기록하는 배열을 만들고, 위에서처럼 한 구간의 길이 / (이 구간에 설치된 휴게소의 개수 + 1) 를 통해 그 구간 안의 세부 구간들중 가장 긴 구간을 구한다. 휴게소를 설치하지 않았다면 한 구간 전체가 도출될 것이고, 휴게소를 2개 설치했다면 그 구간을 3부분으로 균일하게 나눴을 때의 최대 구간이 도출될 것이다. 새 휴게소의 위치를 기록하지 않아도, 이 구간 안에서 나눠진 세부 구간들의 최대 길이를 계산해낼 수 있다.

((arr[i] - arr[i-1]) / (section[i] + 1)) + (((arr[i] - arr[i-1]) % (section[i] + 1) != 0) ? 1 : 0)

 

1) 고정 구간 안에서 나올 수 있는 가장 긴 구간을, 고정 구간의 길이에서 설치된 휴게소 개수로 나누어서 찾아낸 다음, 2) 해당 구간에 휴게소를 1개 더 설치하며 최대 길이 구간을 줄여나간다. 이 과정을 m번 반복한다. 전체 과정은 O(NM) 이므로 여유롭다.

 

전체 코드

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

class Main {
    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());

        if (n == 0) System.out.println((l / (m + 1)) + ((l % (m + 1) != 0) ? 1 : 0)); // n이 0이면, 0부터 l까지의 구간을 (m + 1) 로 나눴을 때의 최대 구간을 출력한다.
        else {
            st = new StringTokenizer(br.readLine());

            int[] arr = new int[n+2];  // 0 ~ l 까지의 휴게소 구간 배열
            for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(st.nextToken());
            arr[n] = 0;
            arr[n+1] = l;
            Arrays.sort(arr);

            int[] section = new int[n+2]; // 구간마다 세운 새로운 휴게소 개수
            Arrays.fill(section, 0);

            int max_section = 0; // 현재 최대 길이 구간
            int max_idx = 0; // 현재 최대 길이 구간의 인덱스
            for (int i = 0; i < m + 1; i++) { // 휴게소를 m번 설치하고, m+1번 째에는 max_section 만 얻어오기 위함
                max_section = 0;
                max_idx = 0;

                for (int j = 1; j < n + 2; j++) { // 휴게소를 하나 더 균일하게 설치했을 때가 최대 길이 구간이라면
                    if (max_section < ((arr[j] - arr[j-1]) / (section[j] + 1)) + (((arr[j] - arr[j-1]) % (section[j] + 1) != 0) ? 1 : 0)) {
                        max_section = ((arr[j] - arr[j-1]) / (section[j] + 1)) + (((arr[j] - arr[j-1]) % (section[j] + 1) != 0) ? 1 : 0);
                        max_idx = j;
                    }
                }
                section[max_idx] += 1; // 최대 길이 구간인 곳에 휴게소 하나 더 설치
            }

            System.out.println(max_section); // 현재 최대 길이 구간 출력
        }
    }
}