반응형
문제
https://www.acmicpc.net/problem/2805
2805번: 나무 자르기
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보
www.acmicpc.net
풀이
조건을 만족하는 최대 값을 구하기 때문에 매개변수 탐색이라고 할 수 있습니다.
높이를 x로 설정한다면, 가져갈 수 있는 나무는 나무가 x보다 길다면 나무길이 - x 일 것이고 x보다 작다면 0일 것입니다.
따라서 max(나무 길이 - x, 0)으로 나타낼 수 있습니다.
가져갈 수 있는 나무가 m 이상이 된다면,
최대 높이를 구하기 위해 높이를 올려서 확인하고, m보다 작다면 높이를 낮춰주어야 합니다.
여기서 이분탐색을 사용해서 조건을 만족하는 최대 높이를 구할 수 있습니다.
소스코드
후기
랜선 자르기 문제와 비슷한 문제였습니다.
이분탐색에 대한 이해가 있다면 쉽게 풀 수 있는 문제였습니다.
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 12015 가장 긴 증가하는 부분 수열 2 (Swift) (0) | 2023.04.20 |
|---|---|
| [BOJ] 백준 2110 공유기 설치 (Swift) (0) | 2023.04.13 |
| [BOJ] 백준 1654 랜선 자르기 (Swift) (0) | 2023.04.13 |
| [BOJ] 백준 1920 수 찾기 (Swift) (0) | 2023.04.12 |
| [BOJ] 백준 11444 피보나치 수 6 (Swift) (0) | 2023.04.12 |
