둠치킨
코딩하는 둠치킨
둠치킨

블로그 메뉴

  • 홈
  • 분류 전체보기 (225) N
    • 프로그래머스 (1) N
      • 해시 (1) N
    • BOJ (176)
      • 스택 (14)
      • 큐 (5)
      • 덱 (4)
      • 그래프 (31)
      • 배열 (8)
      • 재귀 (12)
      • 브루트 포스 (2)
      • 그리디 알고리즘 (7)
      • 다이내믹 프로그래밍 (14)
      • 백트래킹 (24)
      • 기하학 (4)
      • 트리 (4)
      • 구현 (14)
      • 수학 (3)
      • 맵 (1)
      • 다익스트라 (2)
      • 누적합 (5)
      • 유니온 파인드 (1)
      • 분할 정복 (2)
    • 자료구조 (15) N
      • 스택 (3)
      • 큐 (5)
      • 덱 (2)
      • 그래프 (1)
      • 트리 (2) N
      • 힙 (1)
      • 정렬 (1)
    • C++ (11)
      • 모두의코드 (2)
      • Effective C++ (3)
      • C++ STL (6)
    • 컴파일러 (1)
    • OS (17)
    • 컴퓨터 구조 (2)
    • Unreal Engine 5 (2)

공지사항

전체 방문자
오늘
어제

인기 글

최근 글

태그

  • BFS
  • boj
  • Bruteforce
  • C
  • C++
  • C++ STL
  • Cache Memory
  • deadlock
  • DFS
  • Effective C++
  • java
  • Mutex
  • next_permutation
  • os
  • Process
  • rotate
  • semaphore
  • spin lock
  • STL
  • STL C++
hELLO · Designed By 정상우.
둠치킨

코딩하는 둠치킨

BOJ

2110번: 공유기 설치

2024. 9. 27. 14:52

2110번:  공유기 설치

사용 언어: C++

 

풀이

공유기들 사이의 거리를 최대한 크게 둬야하기 때문에 이분 탐색을 생각하면 된다.

1) 이분 탐색을 쓰려면 일단 정렬 -> sort

2) 공유기 사이의 최대 거리 구하기

 

최대 거리를 구하려면 일단 첫 번째 집과 마지막 집을 시작과 끝으로 잡고 이분탐색을 시작한다.

두 집의 중간 거리 값이 가능한지 canPlaceRouters(거리)를 통해 확인한다. 저 함수에서는 모든 집들 사이에 받은 (거리)만큼 떨어진 집에 설치가 가능한지 확인하고, 설치가 가능하면서 설치한 개수가 총 개수와 같다면 true를 리턴한다.

canPlaceRouters가 true라면 low = mid + 1로 mid 거리를 벌려 더 큰 경우가 가능한지 확인하고, 만약  false라면 high = mid - 1로 더 작은 거리에서는 가능한지 확인한다.

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

int N, C;
vector<int> houses;

// 공유기를 주어진 거리 `d` 이상으로 배치할 수 있는지 확인
bool canPlaceRouters(int d)
{
    // 첫 번째 집은 무조건 공유기 설치
    int count = 1;
    // 가장 최근 공유기 설치한 집
    int lastInstalled = houses[0];

    for (int i = 1; i < N; i++)
    {
        // 공유기 설치 가능하면 설치
        if (houses[i] - lastInstalled >= d)
        {
            count++;
            lastInstalled = houses[i];
        }
        // 설치된 수가 총 공유기 개수면 return true
        if (count >= C) return true;
    }

    return false; // C개 설치 불가능
}

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

    cin >> N >> C;
    houses.resize(N);

    for (int i = 0; i < N; i++)
    {
        cin >> houses[i];
    }

    // 1. 집 좌표 정렬
    sort(houses.begin(), houses.end());

    // 2. 이분 탐색으로 가장 인접한 공유기 사이의 최대 거리 구하기
    int low = 1;  // 최소 거리
    int high = houses[N - 1] - houses[0];  // 최대 거리
    int answer = 0;

    while (low <= high)
    {
        int mid = (low + high) / 2;  // 중간 거리
        if (canPlaceRouters(mid))
        {
            answer = mid;  // 가능한 거리라면 일단 저장
            low = mid + 1;  // 더 큰 거리 시도
        }
        else
        {
            high = mid - 1;  // 불가능한 거리면 거리 줄이기
        }
    }

    cout << answer << "\n";
}

 

저작자표시 (새창열림)

'BOJ' 카테고리의 다른 글

24479번: 알고리즘 수업 - 깊이 우선 탐색 1  (0) 2024.09.30
1654번: 랜선 자르기  (0) 2024.09.27
11650번: 좌표 정렬하기  (1) 2024.09.26
18870번: 좌표 압축  (0) 2024.09.26
10816번: 숫자 카드 2  (0) 2022.02.04
    'BOJ' 카테고리의 다른 글
    • 24479번: 알고리즘 수업 - 깊이 우선 탐색 1
    • 1654번: 랜선 자르기
    • 11650번: 좌표 정렬하기
    • 18870번: 좌표 압축
    둠치킨
    둠치킨
    코딩 공부를 위한 코딩 블로그 기록 일기

    티스토리툴바