백준 2805 나무 자르기

문제링크 : https://www.acmicpc.net/problem/2805

아이디어

• 접근 1. 브루트포스로 일단 접근
  • 모든 높이에 대해, 모든 나무를 탐색하여 높이의 최대값을 구함
  • O(K * N) = O(1e9 * 1e6) > 시간초과
• 접근 2. 높이를 이진탐색하여, 그떄마다 가져갈 수 있는 나무를 탐색
  • 이떄, 가능한것중에 가장 큰 값을 가져가야함

시간복잡도 계산

• 높이를 이진탐색 : O(lgK)
  • 각 높이에서 모든 나무를 순회 : O(N)
  • 총합 : O(NlgK) = 1e6 * lge9 = 1e6 * 30 = 3e7 > 가능'

자료구조

• 전체 나무 : int[]
  • 나무 최대 길이 : 2e9 > int 가능
• 자르는 나무 높이 총합
  • 최대값 : 나무수 * 나무길이 최대 = 1e6 * 2e9 > long long 사용

코드(C++)

#include <iostream>
 
using namespace std;
typedef long long ll;
 
int tree[1000010];
int N,M;
 
bool chk(int num) {
    ll rs=0;
    for(int i=0; i<N; i++) {
        // 나무 자르고 남은값
        int et = tree[i] - num;
        if(et > 0) rs += et;
    }
    
    if(rs >= M) return 1;
    return 0;
}
 
int binsearch(int st, int en) {
    if(st==en) return st;
    
    // 여기서 (st+en)/2 로 계산하게되면,
    // 가능한 것중 가장 낮은값을 찾게됨
    // 가능한 것중 가장 높은 값 찾기위해 (st+en)/2 로 사용
    int mid = (st+en+1)/2;
    if(chk(mid) == true) return binsearch(mid, en);
    else return binsearch(st, mid-1);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> M;
    // 나무값 먼저 받아옴
    for(int i=0; i<N; i++) cin >> tree[i];
    
    cout << binsearch(0,1e9) << '\n';
    
    return 0;
}
 

문제유형

• 이진탐색 - 케이스를 이분탐색

비슷한 문제

• https://www.acmicpc.net/problem/1300
• https://www.acmicpc.net/problem/1939
• https://www.acmicpc.net/problem/2805
• https://www.acmicpc.net/problem/1654