BOJ 2805 : 나무 자르기
알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/2805 정답을 X라고 가정하자. 즉, X 만큼 자를 때, 적어도 M 미터의 나무를 집에 가져간다. 그러면 X - 1 만큼 나무를 자르면 M 미터 보다 더 많은 나무를 가져가게 되고, X + 1 만큼 나무를 자르면 M 미터 미만의 나무를 집에 가져가게 된다. 따라서 BOJ 1939 : 중량제한처럼 이분 탐색을 이용하여 X를 찾을 수 있다. 먼저 적당한 값 m으로 나무를 잘라보고, 이 값이 M보다 크면 m 보다 큰 값에서 다시 적당한 값을 정한다. 이 값이 M보다 작으면 m보다 작은 값에서 다시 적당한 값을 정한다. 주어지는 나무들의 길이가 1,000,000,000이고 N이 최대 1,000,000이므로, long long t..
2021. 6. 5.