danbibibi
article thumbnail

1. 문제

문제 바로가기> BOJ 1477번: 휴게소 세우기

 

1477번: 휴게소 세우기

첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. N = 0인 경우 둘째 줄은 빈 줄

www.acmicpc.net

 

2. 풀이

M개의 휴게소를 가능한 빈 공간에 모두 세워보는 조합 방식으로는 너무 많은 경우의 수가 있다.

따라서 입력 받은 위치를 정렬하고, "각 휴게소 간 거리 중 최대값"으로 이분 탐색하여 문제를 해결하였다.

( + 거리이기 때문에 low 값을 0이 아닌 1로 설정하였다.)

문제를 풀기 전에 "예제 입력 1"을 손으로 그려보고 문제를 푸니, 문제를 금방 풀 수 있었던 거 같다.
문제를 이해하고, 코딩을 시작하기 전에, 꼭 한번 예제를 손으로 풀이해 보는 시간을 갖는 게 좋은 것 같다!!
이렇게 한 후로 많은 실수를 줄일 수 있게 된 것 같음!!
<cpp />
#include<iostream> #include<algorithm> #define MAX 55 using namespace std; int N; // 현재 휴게소의 개수 int M; // 더 지을 휴게소 개수 int L; // 고속 도록 길이 int restArea[MAX]; // 현재 휴게소 위치 void input(){ cin >> N >> M >> L; for(int i=0; i<N; i++) cin >> restArea[i]; } bool check(int val){ int cur=0, idx=0, cnt=0; // 세워진 휴게소 확인 while (idx < N){ while(cur+val < restArea[idx]){ cur += val; cnt++; } cur = restArea[idx++]; } // 고속도로 끝까지 확인 while(cur+val < L){ cur+=val; cnt++; } return cnt <= M; } void solve(){ // 1. 현재 휴게소 위치 정렬 sort(restArea, restArea+N); // 2. 이분 탐색 int low=1, mid, high=L; while (low <= high){ mid = (low+high)/2; if(check(mid)) high = mid-1; else low = mid+1; } // 3. 휴게소가 없는 구간의 최댓값의 최솟값 cout << low; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); input(); solve(); }

'문제 풀이 > 백준' 카테고리의 다른 글

BOJ 1938번: 통나무 옮기기  (1) 2024.02.18
BOJ 1005번: ACM Craft  (0) 2024.02.18
BOJ 2933번: 미네랄  (0) 2024.01.31
BOJ 2812번: 크게 만들기  (0) 2024.01.30
BOJ 6549번: 히스토그램에서 가장 큰 직사각형  (1) 2024.01.30
profile

danbibibi

@danbibibi

꿈을 꾸는 시간은 멈춰 있는 것이 아냐 두려워하지 마 멈추지 마 푸른 꿈속으로