백준 2437, 저울 - Greedy, 누적 합
https://www.acmicpc.net/problem/2437
1. 아이디어
-
n개의 추들의 조합으로 만들 수 없는 최소 무게 구하기
① n개 추들의 조합으로 만들 수 있는 "최대 무게" = 모든 추들의 무게 합
② n개 추들의 조합으로 만들 수 없는 "최대 무게" = 모든 추들의 무게 합 + 1
③ 작은 무게 ~ 큰 무게 순으로 정렬했을 때,
인접한 추 끼리 무게 차이가 작아야 더 촘촘히(?) 추의 무게 합 구성 가능
-
n개 추들을 무게 작은 순으로 정렬
①에서 유추한 규칙
- 가장 가벼운
[0]
번째 추 ~[i]
번째 추 까지의 무게 누적합
=[0]
번째 추 ~[i]
번째 추들의 조합으로 만들 수 있는 최대 무게
②, ③에서 유추한 규칙
- (
[0]
번째 추 ~[i]
번째 추 까지의 무게 누적합 + 1) < 다음[i+1]
번째 추의 무게인 경우
=> ([0]
번째 추 ~[i]
번째 추 까지의 무게 누적합 + 1) 무게 구성 불가능
2. 자료구조
int[]
: 각 추들의 무게
3. 시간 복잡도
-
배열 정렬: O(n log_2 n)
=> n 최대값 대입: 10^3 log_2 10^3 = 3 x 10^3 log_2 10 ~= 9 x 10^3 -
누적합 더해가며 무게 구성 여부 확인: O(n)
=> n 최대값 대입: 10^3
=> 전체 시간 복잡도: O(n + n log_2 n)
=> n 최대값 대입: (9 x 10^3) + 10^3 = 10^4 << 1억
코드
import java.io.*;
import java.util.*;
public class Main {
static int n; // 추 개수
static int[] weights; // 각 추의 무게
static int minSum; // 출력, 입력 추 조합으로 만들 수 없는 최소 무게 합
static void solution() {
int sum = 0; // 추 무게 누적합
for (int i = 0; i < n; i++) {
// ([0]번째 추 ~ [i]번째 추 까지의 무게 누적합 + 1) < 다음 [i+1]번째 추의 무게인 경우
// ※ 최초 누적합(sum = 0) + 1 = 1 < weights[0] 비교하여, 무게 1 만들 수 있는지 확인
if (sum + 1 < weights[i]) {
// ([0]번째 추 ~ [i]번째 추 까지의 무게 누적합 + 1) 무게 구성 불가능
minSum = sum + 1;
return;
}
sum += weights[i];
}
// [0]번째 추 ~ [n-2]번째 추 까지의 무게 누적합을 구성 가능한 경우
// => (모든 추의 무게 누적합 + 1) 무게 구성 불가능
minSum = sum + 1;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(
new InputStreamReader(System.in)
);
StringTokenizer st;
n = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
weights = new int[n];
for (int i = 0; i < n; i++)
weights[i] = Integer.parseInt(st.nextToken());
Arrays.sort(weights);
solution();
System.out.println(minSum);
}
}
Author And Source
이 문제에 관하여(백준 2437, 저울 - Greedy, 누적 합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@silver_star/백준-2437-저울-Greedy-누적-합저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)