백준 2437 - 저울, 문제풀이, 프로그래머스, 알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, 풀이과정, Leetcode, 릿코드, 코딩테스트, Tech interview, search, greedy, baekjoon, acmicpc

 

 

 

 

// Process

// 1. Input total, weights

// 2. 입력 weights는 체크한다.

// 3. Sort weights

// 4. 체크배열을 순회한다.

//  4.1. weights로 무게 잴 수 있는지 확인한다.

//  4.2. 가능하면 넘어가고, 불가하면 저장하고 빠져나간다.

// 5. 불가 저장값 반환한다.

 

 

import java.io.*;

import java.util.*;



class Scale {

    public static void main(String args[]) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int total = Integer.parseInt(br.readLine());

        int[] weights = new int[total];

        // 2
        StringTokenizer tokenizer = new StringTokenizer(br.readLine(), " ");

        for (int i = 0; i < total; ++i) {
            weights[i] = Integer.parseInt(tokenizer.nextToken());
        }

        // 3.
        Arrays.sort(weights);

        // 4.
        int minAnswer = 0;
        int number = 1;
        while (minAnswer == 0) {

            if (!isEnableToWeight(weights, number)) {
                minAnswer = number;
            }
            ++number;
        }
        System.out.println(minAnswer);
    }

    public static boolean isEnableToWeight(int[] weights, int weight) {
        for (int i = weights.length-1; weight > 0 && i >= 0; --i) {
            if (weights[i] <= weight) {
                weight -= weights[i];
            }
        }

        if (weight != 0)
            return false;
        else
            return true;
    }

}