백준 1477번 - 휴게소 세우기

구현 방법

이 문제는 여러 가지의 풀이를 생각해 볼 수 있다.

1. 절차적인 방법
   dfs 을 사용하여 구현하는 방법이 있을 것이다.
   각 구간의 길이를 구하고 각 구간에 몇 개의 휴게소가 추가될 수 있을 지를 결정하는 방식으로 구현될 수 있다.
   이렇게 구현했을 때 시간 복잡도는 C(N + M, M) * (N + 1) 이 되어 지수적으로 시간 복잡도가 상승한다.
2. dp
   dp를 사용하는 방식에서 중요한 것은 배열, 점화식, 초기값이다. 
   배열을 결정할 때 독립변수를 결정해야 하는데 이 문제에서는 구간 인덱스와 휴게소 개수일 것이다.
   시간 복잡도는 O(N * M * M) 이고 실제 문제에서 입력값이 제한되어 있기 때문에 시간 안에 해결할 수 있다.
3. 그리디 변형
   가장 큰 구간에 휴게소를 추가하는 방식으로 풀이가 가능하다. 이 때, 휴게소를 해당 구간에 넣었을 때 구간의 길이는 (휴게소 개수 + 1) 로 나눠진 값이다. 그래서 총 M 개의 휴게소를 추가하면 된다. 
   이 때, 가장 큰 구간을 꺼내기 위해서 우선순위 큐를 활용한다.
   시간 복잡도는 우선순위 큐 삽입 (logN) * 휴게소 수(M) 이다. 

코드

1. 절차적인 방법(dfs)

void dfs(int idx, int num){
	// 마지막 idx 인 경우
    if() ~
    
    for(int i = 0; i <= num; i++){
    	arr[idx] = i;
    	dfs(idx + 1, num - i);
    }
}

 

2. dp

for(int i = 0; i <= N; i++){
	for(int j = 0; j <= M; j++){
    	for(int k = 0; k <= j; k++){
        	int mxSeg = (distance[i] + k) / (k + 1);
            int candidate = Math.max(dp[i - 1][j - k], mxSeg);
            dp[i][j] = Math.min(dp[i][j], candidate);
        }
    }
}

 

3. 그리디

package greedy;

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

public class BJ1477 {
    private static int N, M, L;
    private static int[] locations;
    private static int[] distances;
    public static void main(String[] args) throws IOException {
        readInput();
        solve();
    }

    private static void readInput() 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());
        L = Integer.parseInt(st.nextToken());

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

    private static void solve(){
        Arrays.sort(locations);
        
        PriorityQueue<Section> pq = new PriorityQueue<>((a, b) -> {
            return b.distance - a.distance;
        });

        // 초기화
        for(int i = 0; i <= N; i++){
            distances[i] = locations[i + 1] - locations[i];
            pq.add(new Section(i, 1, distances[i]));
        }

        for(int i = 0; i < M; i++){
            Section s = pq.poll();
            int distance = distances[s.idx]/(s.num + 1) + (distances[s.idx] % (s.num + 1) == 0 ? 0 : 1);
            pq.add(new Section(s.idx, s.num + 1, distance));
        }

        System.out.println(pq.poll().distance);
    }

    private static class Section{
        private int idx;
        private int num;
        private int distance;

        public Section(int idx, int num, int distance){
            this.idx = idx;
            this.num = num;
            this.distance = distance;
        }
    }
}

결과