[백준] 1477 휴게소 세우기

문제 :

www.acmicpc.net/problem/1477

1477번: 휴게소 세우기

 

분석 :

풀땐 몰랐는데 예전 라우터 문제와 비슷한 방식의 문제다!! 

 

생각한 틀린 방법 :

for문을 한번씩 돌때마다 가장 간격이 큰 휴게소 지점을 반으로 나눠 그 지점에 휴게소를 세운다.

//
//  1477_rest.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/04/05.
//

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>


using namespace std;
int already, will, dis;
int min_num = 0;
vector<int> v;

void set_rest(){
    int tmp_min = 0, tmp_idx;
    int tmp_tmp_idx = 0;
    while(will--){
        sort(v.begin(), v.end());
        for(int i = 1; i < (int)v.size(); i++){
            if(tmp_min < (v.at(i) - v.at(i - 1))){
                tmp_min = v.at(i) - v.at(i - 1);
                tmp_tmp_idx = v.at(i - 1) + v.at(i);
            }
        }
        
        tmp_idx = tmp_min / 2;
        tmp_min = 0;
        v.push_back(tmp_tmp_idx/2);
    }
    
    sort(v.begin(), v.end());
    for(int i = 1; i < (int)v.size(); i++){
        if(min_num < (v.at(i) - v.at(i - 1))){
            min_num = v.at(i) - v.at(i - 1);
        }
    }
    
}

int main(){
    cin >> already >> will >> dis;
    v.push_back(0);
    for(int i = 0; i < already; i++){
        int temp;
        cin >>temp;
        v.push_back(temp);
    }
    v.push_back(dis);
    set_rest();
    return 0;
}

 

하지만 이렇게 풀면 안되는게 지점에 휴게소가 여러개 들어갈 수 있다는 점!

예를 들어 {0, 300, 500} 에 휴게소 두개를 세우고 싶을 때 -> {0, 150, 300, 400, 500}도 되지만 {0, 100, 200, 300, 500}으로 나누어질 수도 있다는 것이다. 따라서 이렇게 풀면 안되고 이진 탐색 방법으로 접근해야 하는 것 같다. 

다른 블로그 글들 보면 n이 작아 꼭 이진 탐색으로 풀지 않아도 된다 하는데 나는 이진 탐색 방법으로 풀고자 하였다.

 

0, dist를 두번째줄 시작 전, 끝 벡터에 넣어주고 

left와 right를 잡아준다. 

mid는 새롭게 세울 휴게소의 위치다. 

그리고 rest는 두 휴게소 사이 세울 수 있는 편의점의 개수를 의미하며 이것이 세우기로한 편의점 개수보다 많다면 left를 mid + 1하여 간격을 줄인다. 

반다로 세우고자 한 편의점의 개수보다 적다면 right를 mid - 1 하여 간격을 늘리는 것이다. 

 

c++ 코드 :

//
//  1477_rest.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/04/05.
//

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int already, will, dis;
int min_num = 0;
vector<int> v;
void set_rest(){
    sort(v.begin(), v.end());
    int left = 1; int right = dis;
    while(left <= right){
        int mid = (left + right)/2;
        int rest = 0;
        for(int i = 1; i < (int)v.size(); i++){
            //0이 나누어 떨어지면 기존에 있던 위치에 다시 세우는 것이므로 
            if((v.at(i) - v.at(i - 1)) % mid == 0){
                rest += (v.at(i) - v.at(i - 1) - 1)/ mid;
            }else{
                rest += (v.at(i) - v.at(i - 1))/ mid;
            }
        }
        if(rest > will) left = mid + 1;
        else right = mid - 1;
    }
    cout << left << '\n';
}

int main(){
    cin >> already >> will >> dis;
    v.push_back(0);
    for(int i = 0; i < already; i++){
        int temp;
        cin >>temp;
        v.push_back(temp);
    }
    v.push_back(dis);
    set_rest();
    return 0;
}