白駿2437、秤-Greedy、積算

https://www.acmicpc.net/problem/2437

1.アイデア

n個の組み合わせられない最小重量を求めます
①n個の枢椎を組み合わせた「最大重量」=全枢椎の重量の和
②n複数の枢椎に組合わない「最大重量」=全枢椎の重量の和+1
③小重量~大重量の並べ替えの場合、
隣接するピボット間の重量差が小さいほど密(?)ピボット重量と

重量の小さい順にn個のピボットを並べます

類推規則

最軽量[0]第1ダイヤル~[i]から第1ダイヤルまでの積算重量
=[0]2番目のピボット[i]2番目のピボットを組み合わせた最大重量

②、③の類推規則

([0]第1ダイヤル~[i]から第1ダイヤルまでの積算重量+1)<次[i+1]第1ダイヤルまでの重量
=>([0]第1ダイヤル~[i]から第1ダイヤルまでの積算重量+1)再構成不可

2.資料構造

int[]:枢椎当たりの重量

3.時間複雑度

配列順:O(n log 2 n)
=>n最大値代入:10^3 log 210^3=3 x 10^3 log 2~=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);
	}
}