문제
백준 2437번 - 저울
아이디어
- 추 무게를 정렬하여 가벼운 무게부터 탐색할 수 있도록 한다.
- 추의 최소 무게 1을 시작으로 오름차순 정렬된 추의 무게들을 하나씩 더해간다. 이 값을
min
이라 한다.
- 현재 추의 무게가
min
값보다 작거나 같다면 이 추를 추가하여 측정할 수 있는 무게의 범위를 갱신한다.
- 현재 추의 무게가
min
값보다 크다면 이때 min
값이 측정할 수 없는 최소 무게이다.
예상 시간 복잡도
코드 구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BJ_2437 {
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];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
int min = 1; //추의 측정 가능 무게 범위
for (int num : arr) {
if (num > min) {
break;
}
min += num;
}
System.out.println(min);
}
}