2437번 : 저울

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

2437번: 저울

 

 

문제

 

 

코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); sc.nextLine();

        int arr[] = new int[n];
        for(int i=0;i<n;i++) {
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        
        int accumulate = 1;
        for(int i=0;i<n;i++) {
            if(accumulate<arr[i]) break;
            accumulate += arr[i];
        }
        System.out.println(accumulate);
    }
}

 

 

해결방법

문제를 어떻게 풀까 고민을 계속하다 결국 풀지 못하고 다른 사람의 풀이를 보았다. 참고

 

핵심은 기존 x~y까지 측정할 수 있다고 가정할 때 무게가 5인 추가 새로 들어오면 기존에 측정할 수 있었던 무게 + 5까지 측정할 수 있으므로 구간은 x~(y+5)로 변한다.

그렇다면 측정값의 최소는 어떻게 구할까? 현재 추들의 무게의 합보다 새로 들어온 추의 무게가 "더 큰 경우"에 현재 추들의 무게의 합이 최솟값이 된다. 왜냐하면 이어질 수가 없기 때문이다. 자세한 풀이는 참고링크를 통하면 볼 수 있다.

 

현재 추들의 무게의 초기값을 1로 설정한 이유는 측정할 수 없는 값의 최솟값은 측정 가능한 값보다 1 커야 하기 때문이다.