백준 2437번: 저울 (Java)

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

2437번: 저울

 

 

 

 

 

 

 

 

---

 

풀이

처음에는 별 생각없이 DP 식으로 접근했다가, 메모리 초과가 나왔습니다. 그래서 다른 방식으로 풀었습니다.

저울추를 오름차순으로 정렬합니다. 저울추가 0개일 때에는 잴 수 없는 최소 무게가 1이므로, 1에서 시작합니다. 저울추에 대해 for문을 돌면서, 만약 현재 저울추의 무게가 현재 잴 수 없는 최소 무게보다 클 경우 현재 잴 수 없는 최소 무게는 앞으로도 잴 수 없습니다. 반대로, 현재 저울추의 무게가 현재 잴 수 없는 최소 무게보다 작거나 같을 경우, 잴 수 없는 최소 무게는 현재 저울추 무게만큼 더 커집니다.

 

 

코드

import java.io.*;
import java.util.*;
 
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[] weights = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            weights[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(weights);
        int ans = 1;
        for (int w: weights) {
            if (w > ans) {
                System.out.println(ans);
                return;
            }
            ans += w;
        }
        
        System.out.println(ans);
    }
}