목록2023/01/29 (1)
똥그래미 코딩공장
백준 2805번(나무 자르기) 파이썬
https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이 문제는 이분탐색의 "응용" 문제이다. 저번에 풀었던 [수 찾기] 문제 보단 어려웠지만 다 풀고나니 할만 했던거 같다. 이 문제는 가장 긴나무를 end로 하고 그 중간값을 mid로 하여 각각의 나무의 mid부터 end까지의 길이의 합을 더하여 m보다 크거나 같을 경우 mid는 조건에 부합하는 절단선의 높이이기 때문에 answer 리스트에 넣어준다 그 다음 ..
Algorithm
2023. 1. 29. 00:57