백준 2805 나무 자르기 쉬운 풀이(C++/CPP)

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

문제 접근

• 모든 높이를 기준으로, 전체 나무 순회 >> O(M*N) >> 2e9 * 1e6 >> 시간초과
• 자르려는 높이 증가할수록 얻을수 있는 나무의 길이가 감소 >> 선형적이므로 이진탐색 사용 가능
  • 자르려는 높이를 이진탐색 O(lgM)
  • 이때 나무 순회하면서 얻을 수 있는 나무를 구함 >> O(N)
  • O(N*lgM)
• Lower vs Upper
  • 이진 탐색 하는것을 그래프로 그려봤을때
  • X축 : 자르려는 높이, Y축 : 얻게되는 나무의 수
  • 같은값이 없을때 더 낮은 높이를 설정해야함 > UpperBound
  • 더 높은 높이를 설정할 경우, 얻게 되는 나무의 수가 부족한 현상 발생

시간복잡도 계산

• 자르려는 높이를 이진탐색 O(lgM)
• 이때 나무 순회하면서 얻을 수 있는 나무를 구함 >> O(N)
• O(N*lgM)

인트 계산

• 이진탐색 시 필요한 나무길이 : 나무길이 최대 1e6 * 2e9 >> 2e15 >> 인트 사용 불가, long long
  • 나무 높이 : 1e9 이하 >> 인트 사용 가능

코드

#include <iostream>
 
using namespace std;
typedef long long ll;
 
int tree[1000010];
 
int N,M;
 
ll chk(int mid) {
    ll rs=0;
    for(int i=0; i<N; i++) {
        rs += max(tree[i]-mid, 0);
    }
    return rs;
}
 
int binsearch(int M, int st, int en) {
    if(st==en) return st;
    
    int mid = (st+en+1)/2;
    if(chk(mid) >= M) return binsearch(M, mid, en);
    else return binsearch(M, st, mid-1);
}
 
int main() {
    cin >> N >> M;
    for(int i=0; i<N; i++) cin >> tree[i];
    
    cout << binsearch(M,0,1e9) << '\n';
    
    return 0;
}
 

문제유형

• 이진탐색 - 케이스
  • 이진 탐색 문제 중 정답이 되는 값을 이진탐색 하는 문제
  • 이와 반대 유형으로 '이진탐색 - 모든 케이스'
    • 모든 케이스에 대해서, 연산을 이진탐색 해주는 유형
      

비슷한 문제

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