[BAEKJOON] 1477 휴계소 세우기 (C++, Java)

엄청나게 애먹은문제다, 굳이 이분탐색으로 풀지않아도 풀린다는 풀이가 많았다.

하지만 그런 풀이들이 대체적으로 이해가되지않았고... 많은 참고와 도움끝에 겨우 이해한 정도로 풀었다...

 

Java를 배우면서 한번더 풀어보았다.

이분탐색에대해서 그래도 기초문제들을 많이풀었엇고, 그렇게 큰 조건이 주어지지 않은 문제였기 때문에 수월하게 풀엇다.

---

[ 문제 ]

휴게소 세우기 성공분류

2 초

128 MB

1755

722

534

41.850%

문제

다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다.

다솜이는 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다. 휴게소는 정수 위치에만 세울 수 있다.

다솜이는 이 고속도로를 이용할 때, 모든 휴게소를 방문한다. 다솜이는 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 한다. (반드시 M개를 모두 지어야 한다.)

예를 들어, 고속도로의 길이가 1000이고, 현재 휴게소가 {200, 701, 800}에 있고, 휴게소를 1개 더 세우려고 한다고 해보자.

일단, 지금 이 고속도로를 타고 달릴 때, 휴게소가 없는 구간의 최댓값은 200~701구간인 501이다. 하지만, 새로운 휴게소를 451구간에 짓게 되면, 최대가 251이 되어서 최소가 된다.

입력

첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나 같은 정수이다. 모든 휴게소의 위치는 중복되지 않으며, N+M은 L보다 작다. 둘째 줄에, 휴게소의 위치가 공백을 사이에 두고 주어진다.

---

[ 조건 ]
전체 도로의길이가주어지고, 시작점이 0이라는 부분에서 처음과 끝부분에 0과 최대도로의길이를 설정해주어야한다.

이분탐색할 목표는 휴계소가 지어질 수 있는 구간의 길이이다.

이때,  휴계소간의 거리에 지을 수 있는 휴계소의 개수를 판별하고,

만약 휴계소간의거리가 목표한 거리와 같다면, 이경우는 휴계소를 지을 수 없기때문에 배제시켜주어야한다.

 

두번째 풀때도 위 마지막조건을뒤늣게 판별해준것과

left<=right 조건과, result <= M 부분에서 mid값을 가져가는 부분에 디버깅을 좀더 한것같다.

---

[ 핵심소스코드 / C++ ]

while (left <= right) {
    int cnt = 0;
    int mid = (left + right) / 2;
    for (int i = 0; i < v.size() - 1; i++) {
        int dist = v[i + 1] - v[i];
        if (dist / mid > 0) {
        if (dist%mid==0)
            cnt += (dist - 1) / mid;
        else
            cnt += dist / mid;
        }
    }
    if (cnt <= more) 
        right = mid - 1;
    else
        left = mid + 1; 
}

[ 전체소스코드 / C++ ] 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#pragma warning(disable:4996)
using namespace std;

#define endl "\n"
#define tap "\t"
#define MAX 1001

int now, more, Max;
int result;

vector <int> v;

void solve() {
    int left = 0, right = Max;
    while (left <= right) {
        int cnt = 0;
        int mid = (left + right) / 2;
        for (int i = 0; i < v.size() - 1; i++) {
            int dist = v[i + 1] - v[i];
            if (dist / mid > 0) {
                if (dist%mid==0)
                    cnt += (dist - 1) / mid;
                else
                    cnt += dist / mid;
            }
        }
        if (cnt <= more)
            right = mid - 1;
        else
            left = mid + 1; 
    }
    cout << left;
}

int main() {
#ifdef _CONSOLE
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> now >> more >> Max;

    v.push_back(0);
    for (int i = 0; i < now; i++) {
        int temp;
        cin >> temp;
        v.push_back(temp);
    }
    v.push_back(Max);
    
    sort(v.begin(), v.end());
    solve();
}

[ Java ] 

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class _1477_휴계소세우기 {
    static int N, M, L;
    static ArrayList<Integer>rest = new ArrayList<>();
    static void init() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        L = sc.nextInt();
        rest.add(0);
        rest.add(L);
        for(int i=0;i<N;i++)
            rest.add(sc.nextInt());
        Collections.sort(rest);
        solve();
    }
    static void solve() {
        int res=0;
        int left=0, right=L;
        while(left<=right) {
            int mid = (left+right)/2;
            int result = build(mid);
            if (result <= M) {
                res=mid;
                right = mid-1;
            }
            else
                left = mid+1;
        }
        System.out.println(res);
    }
    static int build(int mid) {
        int cnt=0;
        for(int i=0;i<rest.size()-1;i++) {
            int value = rest.get(i+1)-rest.get(i);
            if (value%mid == 0)
                cnt+=value/mid -1;
            else
                cnt+=value/mid;
        }
        return cnt;
    }
	public static void main(String[] args) {
        init();
    }
}