Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 자바PS
- 시뮬레이션
- deque
- DFS
- 01BFS
- 네트워크플로우
- 취득후기
- BFS
- 세그먼트트리
- 백준코딩테스트
- java
- 재귀함수
- COSPROJAVA1급
- 게더타운시작
- 엘라스틱서치
- 완전탐색
- 이젠 골드구현도 어렵네..
- 다익스트라
- 우선순위큐
- COSPRO
- YBMCOS
- spring
- 다이나믹프로그래밍
- PS
- QUICKSTARTGUIDE
- GatherTown
- dp
- 알고리즘
- 백준
- 구현
Archives
- Today
- Total
공부공간
BOJ - 2805 ) 나무자르기 본문
https://www.acmicpc.net/problem/2805
이분탐색으로 나무를 자르는 문제이다.
절단기의 H를 설정해주면 나무배열에서 H이상의 값을 가진나무들과 H의 차만큼 가져갈수있는 나무가 생긴다.
그때에, 필요한 나무를 가져가면서 설정할수있는 H의 최댓값을 찾는문제이다.
이분탐색으로 LEFT = 0 , RIGHT = *max_element()를 사용하여서 백터에서 가장 큰 값을 가지고 시작하였다.
처음에 LEFT를 나무의 가장 작은 *min_element()로 설정하니 자꾸 틀렸다고 나와서 생각해보니
필요한 나무길이가 많아서 최소작은 나무보다 더 아래쪽으로 절단기를 설정해주는 경우가 있었다.
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
38
39
40
41
42
43
44
45
46
47
48
49
50
|
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
long long N , M , mid, cut_sum, ans;
vector <long long> wood;
void input() {
cin >> N >> M ;
for (int index = 0; index < N; index++) {
long long t; cin >> t;
wood.push_back(t);
}
}
long long cut(vector< long long> wood, int mid) {
long long sum = 0;
for (auto wood_one : wood) {
if (wood_one > mid) {
sum += (wood_one - mid);
}
}
return sum;
}
int main(void) {
input();
long long left = 0;
long long right = *max_element(wood.begin(), wood.end());
while (left <= right) {
mid = (left + right) / 2;
cut_sum = cut(wood, mid);
if (cut_sum < M) {
right = mid - 1;
}
else {
if (ans < mid) ans = mid;
left = mid + 1;
}
if (cut_sum == M) break;
}
cout << ans;
return 0;
}
|
'알고리즘 > 이분탐색' 카테고리의 다른 글
BOJ - 8983 ) 사냥꾼 (0) | 2020.10.01 |
---|---|
BOJ - 2473 ) 세용액 (0) | 2020.08.28 |
BOJ - 2110 ) 공유기 설치 (0) | 2019.12.17 |
BOJ - 2512 ) 예산 (0) | 2019.12.16 |
Comments