Search
Duplicate
🍇

나무 자르기

주차
14
문제번호
2805
언어
Python
티어
실버
유형
이분탐색
nj_Blog
nj_상태
완료
이해도
풀이
사람
이해도 2
13 more properties

문제

풀이

나무 전체 길이 합이 int 범위를 넘어가기 때문에
long long 으로 해줘야한다.
left 이상 right 미만으로 풀었다.

구현

#include <iostream> using namespace std; int n; long long m; int wood[1000001]; int wood_max; int rec(long long left, long long right) { long long sum; long long mid; mid = (left + right) / 2; if (right <= left + 1) return (mid); sum = 0; for (int i = 0; i < n; i++) if (wood[i] - mid > 0) sum += wood[i] - mid; return (sum < m ? rec(left, mid) : rec(mid, right)); } int solve() { return (rec(0, wood_max + 1)); } int main() { wood_max = -1; cin >> n >> m; for (int i = 0; i < n; i++) { cin >> wood[i]; if (wood_max < wood[i]) wood_max = wood[i]; } cout << solve() << endl; return (0); }
C++
복사