휴게소 세우기

Created

2021/03/23 01:58

문제 번호

1477

카테고리

자료구조

이분탐색

1477번: 휴게소 세우기

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

https://www.acmicpc.net/problem/1477

Memo

Code

제출 날짜

@12/17/2020

메모리

2016 KB

시간

0 ms

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> rp;

int main()
{
    int N, M, L;
    int i;
    int left, right, mid;

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M >> L;
    rp.resize(N + 2);
    rp[0] = 0;

    for (i = 1; i <= N; i++)
    {
        cin >> rp[i];
    }

    rp[N + 1] = L;
    sort(rp.begin(), rp.end());

    left = 1;
    right = L;

    while (left <= right)
    {
        mid = (left + right) / 2;
        int total = 0;

				// by 🐷
				// rp 사이즈는 미리 저장 해두고 사용하는 걸 권장 (매 루프 조건 비교 마다 함수 호출하니까)
				// 이렇게 루프를 돌릴 때는 int i 가 아닌 size_t로 돌려야 해
				// 엄격하게 채점 시 안 돌아가는 코드고, 비교 범위가 서로 다르니 ㅇㅇ..

        for (size_t i = 1; i < rp.size(); i++)
        {

						// by 🐷
						// rp간 차이 - 1 해서 조정한게 멋지네
						// 코드 깔끔하네

            int d = rp[i] - rp[i - 1] - 1;
            total += (d / mid);
        }
        if (total > M)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }

    cout << left;
    return (0);
}
C++
복사