문제 풀이
오늘의 문제 - 백준2512.예산
나의 풀이
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
int left = 0;
int right = -1;
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
right = Math.max(right, arr[i]);
}
int m = Integer.parseInt(br.readLine());
while (left <= right) {
int mid = (left + right) / 2;
long budget = 0;
for (int i = 0; i < n; i++) {
if (arr[i] > mid) {
budget += mid;
} else {
budget += arr[i];
}
}
if (budget <= m) {
left = mid + 1;
} else {
right = mid - 1;
}
}
System.out.println(right);
}
}해결과정
- left, right 에 이진 탐색 범위를 설정
- right 는 배열의 최대값으로 설정한다.
- 각 원소를 배열에 저장하면서 동시에 최대값을 업데이트 하기
- 반복문은 left가 right 보다 크기 전까지 반복하고, 예산은 루프마다 초기화 해주기
- 현재 탐색 중인 값 설정 : mid
- 각 지방에 해당하는 배열을 순회
- 각 원소가 mid 보다 크면 mid를 더하하고, 그렇지 않으면 원소 값을 더하기 - 예산의 합이 총 예산인 m 보다 이하면, mid를 증가시켜 더 큰 값을 탐색(반대는 mid 감소해서 진행)
오늘 배운 점
이분 탐색 / 이진 탐색 (Binary Search)
- 이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
- 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.
- 변수 3개(시작, 중간, 끝)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다.
이분 탐색 방법
-
처음 범위는 인덱스 0부터 끝까지이다. 이 때 중간 인덱스를 mid로 한다.
-
mid의 값와 찾는 원소를 비교한다.
2-1) 찾는 원소와 mid의 값이 같다면 탐색 종료한다.
2-2) mid의 값 < 찾는 원소 일 때 left는 mid + 1로 하여 2)를 다시 반복한다.
2-3) mid의 값 > 찾는 원소 일 때 right는 mid - 1 로 하여 2)를 다시 반복한다. -
만약 right > left가 된다면 해당 배열에 찾는 원소가 없는 것이다.
더 풀어볼 문제
공부중인 개발자