문제 URL : https://programmers.co.kr/learn/courses/30/lessons/43236
코딩테스트 연습 - 징검다리
출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가
programmers.co.kr
접근법 : 좀어려웠던문제인데
정렬한후 그 거리의 차이들을 구한후 어떤 x라는 값보다 작으면 지워줍니다. 그러면 그 gap의 길이는 길어지겠죠?
지워준 갯수가 n보다 큰지 아닌지에 따라 이분탐색을 돌려주면됩니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include <bits/stdc++.h>
using namespace std;
int solution(int distance, vector<int> rocks, int n) {
int answer = 0;
vector<int> gap;
int before = 0;
sort(rocks.begin(), rocks.end());
for (int i = 0; i < rocks.size(); i++) {
gap.push_back(rocks[i] - before);
before = rocks[i];
}
gap.push_back(distance - before);
int first = 0;
int last = distance;
while (first <= last) {
int mid = (first + last) / 2;
int diff = 0;
int cnt = 0;
for (int i = 0; i < gap.size(); i++) {
if (mid > gap[i]+diff) {
diff += gap[i];
cnt++;
}
else
diff = 0;
}
if (cnt > n) {
last = mid - 1;
}
else {
first = mid + 1;
answer = max(answer, mid);
}
}
return last;
}
|
cs |
궁금한점 혹은 모르는점 어떤 질문이라도 댓글은 언제나 환영입니다.
'프로그래머스' 카테고리의 다른 글
| 프로그래머스 124 나라의 숫자 (0) | 2021.07.28 |
|---|---|
| 프로그래머스 큰 수 만들기 (0) | 2021.07.25 |
| 프로그래머스 이중우선순위큐 (0) | 2021.07.22 |
| 프로그래머스 베스트앨범 (0) | 2021.07.22 |
| 프로그래머스 N으로 표현 (0) | 2021.07.22 |
