링크 : www.acmicpc.net/problem/2805
예전에 푼 적이 있던 문제였으나, 기회가 되어 다시 한번 풀었다.
이 문제에서 주의할 점은 다음과 같다.
1. 절단 높이가 나무보다 더 큰 경우에도 절단이 가능하다.
ex : 나무 15, 절단 높이 20 -> 이때 나무를 자르고 남는 길이는 0으로 여긴다.
2. 때문에 절단기에 설정 가능한 높이가 아닌, 최대의 높이를 선정하는 것이 문제다.
3. 나무의 높이를 크게 받을 수 있으므로, 변수형을 잘 설정해야한다.
문제풀이는 다음과 같다.
1. 값을 모두 입력 받는다. 이때, 가장 높은 나무의 값은 따로 저장한다.
2. while문을 설정한다. 조건은 절단 길이의 양 끝 구간을 mini, maxi라고 가정했을때
mini가 maxi이하인 경우에만 while문이 허용된다.
3. mini와 maxi의 중간값을 구한다. 모든 나무의 길이에서 중간값을 뺀 값을 누적한다.
(*이때 나무의 길이가 중간값보다 큰 경우에만 뺀 값을 누적한다. 이 외에는 어차피 0이 누적되니 계산하지 않아도 된다.)
4. 누적된 값이 m이상일 경우, 더 자를 수 있음을 의미한다. 때문에 mini의 값을 중간값의 +1로 설정한다.
5. 누정값이 m 미만일 경우, 해당 값 자제가 불가능이며 동시에 더 자를 수 없음을 의미한다.
때문에 maxi의 값을 중간값의 -1로 설정한다.
6. 결과값으로 maxi를 출력한다.
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
unsigned long long int n, m, mini, maxi, mid, temp, ans =0;
cin >> n >> m;
unsigned long long int trees[n];
for(int i=0; i<n; i++){
cin >> trees[i];
if(trees[i]>=maxi) maxi = trees[i];
}
while(mini<=maxi){
temp = 0;
mid = (mini+maxi)/2;
for(int i=0; i<n; i++) if(trees[i]>mid) temp += trees[i]-mid;
if(temp>=m) mini = mid+1; // 더 짤라야해
else if(temp<m) maxi = mid -1;
}
cout << maxi << "\n";
return 0;
}
'🖥️ CS > Baekjoon Algorithms' 카테고리의 다른 글
#2239번 스도쿠 (C++) (0) | 2020.12.30 |
---|---|
#2470번 두 용액 (C++) (0) | 2020.12.17 |
#1707번 이분 그래프 (C++) (0) | 2020.12.09 |
#14501번 퇴사 (C++) (2) | 2020.12.04 |
#13460번 구슬 탈출 2 (C++) (0) | 2020.11.25 |