[백준(BOJ)] 2805번 : 나무 자르기 - C++[CPP]

www.acmicpc.net/problem/2805

2805번: 나무 자르기

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 이분 탐색

 

---

 

⊙ 문제 접근 과정

 

최적화 문제는 일단 이진 탐색을 떠올리자.

M만큼의 나무를 가져가면서 절단기로 설정할 수 있는 높이의 최댓값을 구하는 문제이다.

 

시작 값은 0, 끝 값은 입력받은 값 중 가장 큰 값으로 설정했다.

그리고 이진 탐색으로 범위를 좁혀 문제를 해결했다.

 

 

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n,m;
vector<int> tree;

int main() {
    cin >> n >> m;

    for(auto i =0; i<n;i++) {
        int x;
        cin >> x;
        tree.push_back(x);
    }

    int start =0;
    int end= *max_element(tree.begin(),tree.end());
    int result=0;

    while(start<=end) {
        long long int total = 0;
        int mid = (start+end) / 2;
        for(auto i =0; i<n;i++) {
            if (tree[i]>mid) total += tree[i] - mid;
        }
        if(total<m) {
            end = mid -1;
        } else {
            result = mid;
            start = mid +1;
        }
    }
    cout << result;
}

---

⊙ 결과

 

 

---

 

 

 

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!