Computer Science & Engineering

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

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

예제

풀이

    이 문제는 이분 탐색으로 접근해야 하는 문제이다. 이분 탐색으로 푸는 문제는 문제 내용에서 힌트를 얻을 수 있다. 이분 탐색 문제는 최대나 최소를 구하는 문제가 많이 나온다. 이 문제도 "C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오."라고 나와있다. 이 부분에서 이분탐색을 이용해야한다는 것을 알아차릴 수 있다.

    이 문제에서 mid로 설정해야할 값은 공유기 사이의 거리이다. 즉 mid보다 큰 차이가 나면 공유기를 하나 설치해야한다는 것이다. 따라서 설치해야하는 공유기의 수를 매번 계산하여 C개의 공유기가 설치될 때의 최대값을 구할 수 있다.

소스 코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

vector<int> arr;

int main() {
    int N, C; cin >> N >> C;
    for(int i = 0; i < N; i++) {
        int a; cin >> a;
        arr.push_back(a);
    }
    sort(arr.begin(), arr.end());
    int left = 1, right = arr[arr.size() - 1] + 1;
    for(int i = 0; i < 30; i++) {
        int mid = (left + right) / 2;
        int pos1 = arr.front();
        int pos2;
        int wifi = 1;
        for(int j = 1; j < arr.size(); j++) {
            pos2 = arr[j];
            int dist = pos2 - pos1;
            if(dist >= mid) {
                wifi++;
                pos1 = pos2;
            }
        }
        if(wifi >= C) 
            left = mid;
        else
            right = mid;
    }
    cout << left;
}

문제에서 죄표의 최대 값은 10^9이다. 이 값은 2^30보다 작은 값이므로 이분 탐색을 하였을 때 30번만 반복한다면 충분히 커버할 수 있다. 초기 left 값은 1, right값은 가장 큰 인덱스에 1을 더한 값이다. 1을 더한 이유는 정답은 left인데 만약 마지막 인덱스가 정답일 경우 left가 도달하지 못할 수 있기 때문이다. 이 문제는 조건을 만족하는 최대값을 구하는 문제이므로 공유기의 수가 C와 같을 경우에도 left에 mid값을 넣어준다. 그렇다면 C와 같을 때에도 left값은 이를 만족하는 조건에서의 최대 값을 가질 수 있다.

채점 결과

https://programmers.co.kr/learn/courses/30/lessons/64062

문제의 카테고리가 이분탐색인 것을 알지 못하고 문제를 본다면 이분탐색을 이용하여 문제를 풀어야 한다는 것을 알아차리기가 쉽지 않다. 며칠 전에 이분탐색 여러 문제를 풀어보았기 때문에 문제를 읽고 이분탐색을 사용하면 잘 될 것이라고 생각하여 문제 접근 방향을 그렇게 정하였다. 코드는 굉장히 짧다. 아래와 같다.

소스코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> stones, int k) {
    int answer = 0;
    int left = 0, right = *max_element(stones.begin(), stones.end()) + 1; //초기값 설정
    for(int i = 0; i < 30; i++) { //최대 200000000이므로 log2 200000000은 30보다 충분히 작으므로 가능하다.
        int mid = (left + right) / 2; //중간 값을 설정한다. mid명이 건넌다고 생각한다.
        int maxcnt = 0; //가장 많이 건너뛴 수를 저장
        int cnt = 1; //건너뛴 횟수를 그때그때 저장
        for(int i = 0; i < stones.size(); i++) { //징검다리를 하나씩 보며
            if(stones[i] < mid) cnt++; //mid번째 사람이 건널 경우 mid보다 작은 값이 있는 돌은 mid-1명만 건널 수 있으므로 건너뛰게 된다. 따라서 숫자를 센다.
            else { //만약 mid보다 크거나 같은 경우 mid번째 사람도 돌을 밟을 수 있으므로 한번에 건너뛰는 돌의 수는 1로 다시 초기화하고 현재 돌까지 한번에 건너뛴 돌의 수를 계산
                maxcnt = max(maxcnt, cnt); //한번에 건너뛴 돌의 최대값 갱신
                cnt = 1;
            }
        }
        maxcnt = max(maxcnt, cnt); //마지막 돌까지 건널때 cnt값이 갱신되지 않을 수 있으므로 한 번 더 체크
        if(maxcnt <= k) left = mid; //최대 k개 건너 뛸 수 있으므로 가장 많이 건너뛴 수가 k보다 작거나 같은 경우 더 많은 인원이 건널 수 있다고 판단
        else right = mid; //그렇지 않으면 더 적은 사람이 건너 뛸 수 있다고 판단
    }
    answer = left; //등호가 left에 있으므로 left값이 최종 결과
    return answer;
}

이분탐색을 할 때 결과값이 left냐 right냐를 아는 것은 꽤 어렵다. 이 문제는 최대값을 구해야하는 문제이므로 등호를 포함하는 값이 정답이 될 것이다. 글쓴이는 거의 left에 등호를 붙인다.

풀이에서 중요한 부분

    1. left는 초기값으로 0, right는 최대값보다 1 큰 값으로 설정하였다. 1을 더한 이유는 만약 left = 5, right = 6일 경우 mid값으로 갱신했을 경우 mid는 항상 5이므로 left는 6이 될 수 없다. 만약 정답이 6일 경우 오답이 나올 수 있다. 따라서 left는 최소값보다 작은 값, right는 최대값보다 큰 값으로 설정하는 것이 좋다.

    2. for문을 30번 돌았다. stone배열의 원소의 최대값은 200000000(2억)이다. 따라서 2억을 커버할 수 있는 30으로 설정하였다. log2의 200000000은 30보다 훨씬 작은 수이다. 2^30은 대락 10의 9제곱이기 때문이다. 2억을 넘을 수 있는 log값으로 더 작은 수로 설정하여도 충분히 돌아간다.

    3. left가 정답인 이유는 파라매트릭 문제를 여러번 풀어봐야한다. 이 문제에서는 건너뛴 바위의 수가 k보다 작거나 같은 조건에서 가장 큰 값이어야한다. 이때 for문의 가장 마지막에 if(maxcnt <= k) left = mid;라는 코드가 있다. 이 코드가 바로 이전 말과 같은 말이다. 건너뛴 바위의 수가 k보다 작거나 같을 때 left를 mid로 설정하라는 말이다. 더 큰 값이 있을 수 있기 때문이다. 만약 이 조건을 만족하지 않을 경우 right = mid 코드가 실행될 것이다. 따라서 left는 정답이 될 수 있는 조건을 만족하지 않은 상태에서 최대값으로 갱신되기 때문에 left가 최종 정답이 되는 것이다.