[C++] BOJ 1477 - 휴게소 세우기

BOJ 1477 - 휴게소 세우기 (https://www.acmicpc.net/problem/1477)

 

01. 🔎 문제 탐색

N: 기존에 설치된 휴게소 개수 (0 <= N <= 50)
M: 설치해야 할 휴게소 개수  (1 <= M <= 100)
L: 고속도로의 길이 (100 <= 1000)
(N+M < L)

* 길이 L만큼의 고속도로에 M개의 휴게소를 가장 긴 길이가 최소가 되도록 설치하여, 그 길이를 출력

 

새로 설치하는 휴게소는 기존의 휴게소의 위치와 고속도로의 양 끝단에는 설치할 수 없음

01-1. 가능한 시간 복잡도

• 시간제한 2초로 시간 복잡도 O(L*N logL*N) 이하로 구현 가능

01-2. 알고리즘 선택

• 이 문제는 최대 구간의 최소 길이를 탐색하는 문제로 L과 N의 값에 지배
  따라서, 브루트포스의 경우, 시간 복잡도 O(L*N) 으로 구현 가능
• 이진 탐색을 이용하여 구현할 시, 시간 복잡도O(N log L) 을 가짐

02. 📝 코드 설계하기

[공통]

1. N, M, L 에 대해 입력
2. 설치된 휴게소의 위치 N개 입력
3. 각 구간 별 탐색을 위해 정렬

[2-1. 브루트포스]

4. 길이 1부터 L-1까지 반복하며 가능한 최대 구간의 최소 길이를 탐색
    4-1. 각 구간에 대해, 요구 길이를 나누어 설치 가능한 휴게소 개수를 합함
    4-2. 설치 가능한 휴게소의 총합이 M보다 작거나 같을 경우, 최대 구간의 최소 길이로 출력

[2-2. 이진 탐색]

4. 이진 탐색을 위한 (양 끝점을 제외하여) 시작 점 1, 끝 점 L-1을 설정
5. 요구 길이의 기준이 되는 중간 값을 계산
6. 각 구간에 대해 중간 값을 나누어 설치 가능한 휴게소의 개수를 합함
7. 설치 가능한 휴게소의 개수가 M보다 작거나 같을 경우, 더 짧은 길이가 존재할 수 있으므로, 끝 점을 mid - 1로 당김
8. 설치 가능한 휴게소의 개수가 M보다 클 경우, 요구된 M을 초과하므로, 시작 점을 m + 1로 설정해 요구 길이를 늘림
9. 5-8의 과정을 시작 점과 끝 점이 만날 때까지 반복
10. 현재 시작 점의 위치를 출력

03. 🛠️ 시도별 수정

1회차

---

04. 🗝️ 정답 코드

[4-1. 브루트포스]

#include <bits/stdc++.h>
using namespace std;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  vector<int> v;

  int N, M, L;
  cin >> N >> M >> L;

  v.push_back(0);
  v.push_back(L);
  for(int i = 0; i < N; i++){
    int tmp;
    cin >> tmp;
    v.push_back(tmp);
  }
  sort(v.begin(), v.end());

  for(int i = 1; i < L; i++){
    int needed = 0;

    for(int j = 0; j < v.size()-1; j++){
      int cur_len = v[j+1] - v[j];
      needed += ((cur_len - 1) / i);
    }

    if(needed <= M){
      cout << i << "\n";
      break;
    }
  }

  return 0;
}

[4-2. 이진탐색]

#include <bits/stdc++.h>
using namespace std;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  vector<int> v;

  int N, M, L;
  cin >> N >> M >> L;

  v.push_back(0);
  v.push_back(L);
  for(int i = 0; i < N; i++){
    int tmp;
    cin >> tmp;
    v.push_back(tmp);
  }
  sort(v.begin(), v.end());

  int start = 1, end = L - 1;
  while(start <= end){
    int mid = (start + end) / 2;
    int needed = 0;

    for(int i = 0; i < v.size()-1; i++){
      int cur_len = v[i+1] - v[i];
      needed += ((cur_len - 1) / mid);
    }

    if(needed <= M) end = mid - 1;
    else start = mid + 1;
  }

  cout << start << "\n";

  return 0;
}