2805번: 나무 자르기
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보
www.acmicpc.net
핵심요소
- 잘린 나무의 총 길이를 어떠한 방식으로 계산할 수 있을까?
- 절단기의 높이 조절의 기준을 무엇으로 해야 할까?
문제풀이
잘린 나무의 총 길이는 현재의 높이에서 잘릴 수 있는 모든 나무를 비교하면서 값을 하나씩 추가하도록 하자.
절단기의 높이는 잘린 나무의 길이가 원하는 값보다 클 경우 높이고,
잘린 나무의 길이가 원하는 값보다 낮을 경우 낮추도록 한다.
일반적인 브루트 포스로 문제를 풀이하기에는 1초라는 시간이 부족할 것 같다.
O(log n)의 시간복잡도를 가지고 있는 이진 탐색을 이용해서 좀 더 빠른 풀이를 해보도록 하자
이진 탐색을 하기 위해 시작점, 끝점, 현재의 기준점을 정의하고 Loop를 시작한다.
(시작점 + 끝점) // 2로 나누어 중앙값을 찾는다.
각 나무에서 현재 중앙값에 해당하는 높이를 빼고, 남은 값이 존재한다면 잘린 나무의 결과값에 추가한다.
잘린 나무의 총 길이를 비교해 Start Point 값과 End Point 값을 조절한다.
pypy로 제출했습니다.
'항해99 > 알고리즘 마라톤' 카테고리의 다른 글
| 항해99 알고리즘 마라톤 32번 문제 [백준 1260번] (0) | 2021.06.24 |
|---|---|
| 항해99 알고리즘 마라톤 30번 문제 [백준 1021번] (0) | 2021.06.23 |
| 항해99 알고리즘 마라톤 14번 문제 [백준 2869번] (0) | 2021.06.23 |
| 항해99 알고리즘 마라톤 13번 문제 [백준 1436번] (0) | 2021.06.23 |
| 항해99 알고리즘 마라톤 11번 문제 [백준 1011번] (0) | 2021.06.16 |
