백준 2110 공유기 설치

김민형·2022년 2월 8일
0

문제설명

개념설명

개인적으로 좋아하는 문제 유형 중 하나로 이런 종류의 풀이를 Parametric Search라고 한다.이분탐색 중에서 하나의 유형이라고 보면 되는데 이분 탐색을 기반으로 매개변수를 찾아주고 그리고 찾은 매개변수를 key값으로 설정해서 제시된 문제풀이를 할 수 있는가를 탐색하는 방식이다. 우선 이 접근이 가능하기 위해서는 해의 연속성이 있어야 한다.

예를 들어 범위가 [1,10]인 값들 중 최대로 가능한 값을 찾으라고 한다면 최대인 6의 값까지는 모두 가능해야 한다. [1~6]까지는 문제풀이가 가능한 해, [7~10]까지는 문제풀이가 풀가능한 해의 범위로 나뉘어져야 하고 이 구분이 연속성을 가지고 있어야 풀이가 가능하다는 것이다. 왜냐하면 이분탐색을 통해서 매개변수의 값을 찾는 것이므로 현재 내가 설정한 key 값이 문제풀이가 가능한지 여부에 따라서 이분탐색의 범위를 조정해서 가능한 해를 찾아내고 그리고 그 중에서도 가장 끝에 있는 값을 찾음으로 최대/최소값을 찾아주는 것이다.

Parametric Search Template

  // 최댓값을 찾는 경우
  // 찾는 범위를 설정해서 그 안에서 이분탐색으로 값을 찾아가는데
  // 현재 mid값이 가능하면 더 큰 mid 값이 존재하는지 화인하기 위해 s를 조정
  // 현재 mid값이 불가능하면 가능한 해를 찾기 위해 e를 조정
  int s = 1;
  int e = max_size;
  int ans;
  while(s<=e){
    int mid = (s+e) / 2;
    if(solve(mid)){
      ans = mid; 
      s = mid+1;
    }
    else
      e = mid -1;
  }

위와 같은 방식으로 시도해 볼 해의 가능후보들을 이분탐색을 통해서 넣어보면서 탐색하기 때문에 logN시간 안에 탐색을 해 볼 수 있다. 그리고 solve()함수를 통해서 문제에서 구체적으로 요구하는 만족사항을 충족시킬 수 있는지 여부를 확인하는 방식으로 짜주게 되면 각각의 역할이 분담되어 있는 듯한 형식으로 코드가 깔끔하게 짜져서 개인적으로 좋아하는 풀이이다.

접근방식

이번 문제의 구체적인 요구사항을 살펴보자면 공유기들을 C개 설치하여야 하는데 가장 인접한 공유기들 사이의 거리를 최대값을 구하는 것이다. 최소 설치 공유기 개수가 2라는 점을 바탕으로 보면 첫 지점에 하나를 놓고 시작해야 함을 알 수 있다. 그래야 나머지 한 개 이상의 공유기를 설치한다고 했을 때(왼쪽 방향으로 나아감) 오른쪽 끝에 있는 첫 지점에 공유기가 있어야 최대 거리를 유도핼 수 있기 때문이다.

따라서 solve()함수는 C-1개의 공유기를 두번째 지점부터 확인하면서 설치하는데 현재 매개로 받은 길이보다 더 크거나 같아지게 되면 설치하는 방식으로 구성해서 공유기 설치 자체를 할 수 있는지 여부를 확인해준다. 여기서 신경 쓸 부분은 solve()내부에서는 어떤 값이 정밀하게 떨어지는지 여부를 확인하는 것이 아니라 이 값을 가정하면 가능하게 나올 수 있는지 여부만을 확인하는 것이다. 그리고 그 값의 최대/최소의 정밀성은 이분 탐색에서 값을 조정해가는 방식으로 찾게 된다.

C++코드

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

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair <int, int>;

vector <int> arr;
int N, K;

// 첫 지점에다가 하나를 설치하고 시작
// 현재 매개로 받은 거리보다 이전 지점과 현재 지점까지의 거리가 크거나 같아지면 공유기 추가
// 이런 방식으로 공유기 추가해서 주어진 개수 다 설치 가능한지만 확인
bool solve(int key){
  int cnt = 1;
  int cur = 0;
  for(int i=1; i<N; i++){
    if(arr[i]-arr[cur] >= key){
      cnt++;
      cur = i;
    }
  }
  if(cnt >= K)
    return true;
  else
    return false;
}

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

  freopen("inp.txt", "r", stdin);
  
  cin >> N >> K;
  arr.resize(N);

  // 공유기 설치 지점들을 정렬해서 인접거리 최대 구하기 쉽게 설정
  for(int i=0; i<N; i++)
    cin >> arr[i];
  sort(arr.begin(), arr.end());

  // Parametric Search Template
  int s = 1;
  int e = arr[N-1] - arr[0];
  int ans;
  while(s<=e){
    int mid = (s+e) / 2;
    if(solve(mid)){
      ans = mid; 
      s = mid+1;
    }
    else
      e = mid -1;
  }

  cout << ans;
} 

/*
Parametric Search
이분탐색 영역에서 최대/최소 값의 정밀성을 잡아주고
solve() 함수에서는 현재 key값을 바탕으로 가능/불가능 여부만 판단해주기
*/ 
profile
천천히 성장하는 프론트 개발자

0개의 댓글