https://www.acmicpc.net/problem/2805
코드
// 2805
#include <iostream>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
int arr[1000001] = {0};
int max = 0;
for (int i = 0; i < n; i++) {
cin >> arr[i];
if (arr[i] > max)
max = arr[i];
}
int start = 0;
int end = max;
int mid = 0, prev = 0;
while (start <= end) {
mid = start + (end - start) / 2;
long long int height = 0;
for (int j = 0; j < n; j++) {
if (mid < arr[j])
height += arr[j] - mid;
}
if (height < m) {
end = mid - 1;
} else {
prev = mid;
start = mid + 1;
}
}
cout << prev;
return 0;
}이 문제는 나무 절단기의 높이를 조절하여 적어도 M미터의 나무를 얻기 위한 최적의 높이를 찾는 문제이다.
처음에는 min부터 max까지의 값을 범위로 잡고, 하나하나 얻을 수 있는 나무의 길이를 구하는 방식으로 코드를 짰는데 시간초과가 발생했다.
그 뒤로 생각한 방법이 ..!
💡이진탐색
정렬된 데이터 리스트에서 검색 범위를 줄여나가면서 값을 찾는 알고리즘
정렬된 리스트에서만 사용할 수 있음. (리스트의 중간값과 비교하며 찾기때문에 !)
검색이 진행될때마다 검색범위가 절반으로 줄어듦.
방법
1. 배열의 중간 값 가져오기
2. 중간 값과 검색값 비교
- 같다면 종료
- 중간값이 더 크다면 중간값 기준 왼쪽 배열을 대상으로 탐색
- 중간값이 더 작다면 중간값 기준 오른쪽 배열을 대상으로 탐색
- 1과 2 반복
반복의 종료는
1. 검색값과 중간값이 같을때
2. 매 검색대상 배열의 시작지점과 끝 지점을 결정하는 변수가 있는데, 시작지점이 끝 지점보다 클때 (더이상 검색할 범위 없음)
풀이법
이진탐색으로 검색할 배열을 0부터 max를 끝으로 하는 배열으로 설정하고 탐색을 진행한다. (0을 시작으로 하는 정수 배열이기 때문에 이미 정렬된 배열 !)
매 반복문에서 mid(중간값)를 가지고 얻을 수 있는 나무의 높이를 구하고, 유효한 mid 값은 prev 변수에 저장한다. 탐색이 끝난 후 prev에 남아있는 값을 출력하도록 했다.
‼️ 주의할점
1. height의 범위 설정
매 계산마다 나무의 길이를 저장하는 변수인 height를 long long int로 설정해야 했다.
우선 int의 범위는 ~2,147,483,647이고 문제에서 나무의 높이는 최대 1,000,000,000, 나무의 수는 최대 1,000,000이다.
height는 매 나무 높이에서 mid를 뺀 값을 계속 더해가는 것이므로, 이 값들의 합은 int의 범위를 초과할수 있었다 ...!!!!
2. start의 초기값 설정
처음에는 max 값을 구할때 min값도 함께 구한 후, start의 초기값을 min으로 설정했는데 97~98%정도에서 틀렸다는 결과가 떴다.
특정 상황에서는 min값 보다 절단기의 높이를 낮게 설정해야 하는 경우가 있었다.
예를 들어
3 5
3 3 3
위 예시에서 min과 max가 모두 3이지만 절단기의 높이는 1이어야 모아야 하는 높이 5를 넘길수 있다 ..!
