GitHubSeob
C++ / 백준 / 2805 / 나무 자르기 본문
문제
https://www.acmicpc.net/problem/2805
2805번: 나무 자르기
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보
www.acmicpc.net
문제풀이
자른 나무의 길이의 총합이 M이다.
0m짜리 톱으로 자를 수는 없으니 최솟값을 0으로, 최댓값은 1,000,000,000으로 둔다.
while문을 돌면서 이번 차례에 자를 톱의 길이는 (최솟값+최댓값)/2로 두고, 나무 수만큼 돌면서 자른다.
이때 톱보다 긴 나무만 자를 수 있다.
자른 나무의 길이의 총합이 목표치보다 작으면 톱의 길이가 더 짧아야 하므로 max를 mid-1로,
목표치보다 크면 더 긴 톱으로 자를 수 있는 경우가 있으므로 min을 mid+1로 둔다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int N = 0, M = 0;
int idx = 0;
cin >> N >> M;
vector<int>tree(N, 0);
for (idx = 0; idx < N; ++idx)
cin >> tree[idx];
long long min_saw = 1;
long long max_saw = 1000000000;
long long tree_total = 0;
while (min_saw <= max_saw) {
tree_total = 0;
long long mid_saw = (min_saw + max_saw) / 2;
for (idx = 0; idx < N; ++idx)
if (tree[idx] - mid_saw > 0)
tree_total += (tree[idx] - mid_saw);
if (tree_total < M)
max_saw = mid_saw - 1;
else
min_saw = mid_saw + 1;
}
cout << max_saw;
}
'Baekjoon > Silver' 카테고리의 다른 글
C++ / 백준 / 2512 / 예산 (0) | 2021.08.20 |
---|---|
C++ / 백준 / 2110 / 공유기 설치 (0) | 2021.08.19 |
C++ / 백준 / 1654 / 랜선 자르기 (0) | 2021.08.18 |
C++ / 백준 / 10816 / 숫자 카드 2 (0) | 2021.08.17 |
C++ / 백준 / 10815 / 숫자 카드 (0) | 2021.08.17 |