[백준]2437번 저울 [ 다시 풀 것 ]

2437번: 저울

문제 이해하기

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용해 측정할 수 “없는” 양의 정수 무게 중 “최솟값 구하기

• 정확하게 측정해야한다.
  • 그러니까, 예를들어 3, 1, 6, 2, 7, 30, 1 의 저울 추가 주어지면,

  1. 1은 가능( 1)

  2. 2도 가능 ( 1,1)

  3. 3도 가능 (3),(2,1)

  4. 4도 가능 (3,1)(1,1,2)

  5. 5도 가능 ( 3, 1, 1)

  6. 6도 가능 ( 6)

  7. 7도 가능 (7)

  8. 8도 가능 (7,1) , ( 6,1,1 ) .. 등등

  9. 9도 가능

     ....

  10. 21은 불가능.

      ⇒ 정답은 21 . 이런식이 되는 것

• 추의 개수는 최대 1000개, 각 추의 무게는 1 ~ 100만

( 잘못된 과정)

• 무게는 1 ~ 10억 까지..?? 아래에서부터 가능한 것을 찾아나가는 것은 안 될 것 같음.
• 주어진 추 들로 만들 수 있는 경우를 먼서 세팅해둔다면?? → 백트랙킹 방식으로 - 추의 총 개수가 1000개니까. → 총 만들 수 있는 경우는 1000x 1000 = 100만가지 → 100만개를 sorting한다면 → 2000만 정도 ⇒ 정렬된 수에서 사이에 비어있는 수는 “측정할 수 없는 수” 가 될 것.
• 비어있는 수 찾기

  1. 정렬된 수의 첫 번째 수가 1인가?

     → 1이 아니라면, 정답은 1이 될 거임.

  2. Otherwise : 정렬된 수를 순차적으로 접근한다. 앞선 수 +1 이 아니라면 , 여기에 정답이 있는것.

아무튼 이 생각들은 시간,공간복잡도상 불가능

다른 사람 풀이를 보았다

잠깐 누적합에 대해서도 생각했었다. 정렬 시켜놓고, 다음 수가 누적합 이하라면 만들수 있는게 되지 않을까? 라는 생각은 했었는데

의문이었던 점은

• 그 사이 값들도 확실하게 다 만들 수 있는가???

였다.

그런데 이 풀이로 사람들이 풀었다. 어떻게 이게 가능할까??

• 이게 가능한 이유는, 가장 작은 수가 1부터 시작해야하기 때문에( 첫 수가 1이 아니면 정답은 1임 ) .. 어차피 누적합은 순차적으로 증가하게 되어버림.
  

• 1,2 가 주어졌다면, 그 뒤에 어떤 수가 나와야 할까?

  • -> 만들 수 있는 경우 : 1, 2, 3(누적합) .
  • 다음에 나오는 수로 인해 4를 건너뛰게된다면 ..안되겠지? 즉, 다음수는 3(누적합) + 1 이 나와야 한다.
  • 만약 1,2,5 라면 -> 정답은 4 ( 3(누적합) +1 ) 이 된다.

• 1 뒤에는 어떤 수가 나와야 할까?

  • -> 만들 수 있는 수 는 : 1 ( 누적합)
  • 다음에 나오는 수로 인해, 2를 건너뛰게 된다면 .. 안되겠지? 즉, 다음 수는 1(누적합) + 1 이 나와야한다.
  • 만약 1,3 이라면 -> 정답은 2 ( (1(누적합)+ 1 ) 이 된다.

• 주어진 추의 무게가 1,2,4 라면, 이 때는 정답이 뭐가 될까?

  • 만들 수 있는 수 -> 1,2,3,4,5,6,7(누적합)
  • 따라서 이 때 정답은 8 ( 7(누적합) +1 ) 이 된다.

public class Main{
    public static Integer[] input;
    public static int n;

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;
    public static void setting() throws IOException {
        n = Integer.parseInt(br.readLine());
        input = new Integer[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i<n;i++){
            input[i] = Integer.parseInt(st.nextToken());
        }
        // 정렬
        Arrays.sort(input);
    }
    // 첫 번째 원소가 1인지 확인 하는 것도 필요
    /**
     * 1,2 가 주어졌다면, 그 뒤에 어떤 수가 나와야 할까?
     * -> 만들 수 있는 경우 : 1, 2, 3(누적합) .
     * 다음에 나오는 수로 인해 4를 건너뛰게된다면 ..안되겠지? 즉, 다음수는 3(누적합) + 1 이 나와야 한다.
     * 만약 1,2,5 라면 -> 정답은 4 ( 3(누적합) +1 ) 이 된다.
     *
     * 1 뒤에는 어떤 수가 나와야 할까?
     * -> 만들 수 있는 수 는 : 1 ( 누적합)
     * 다음에 나오는 수로 인해, 2를 건너뛰게 된다면 .. 안되겠지? 즉, 다음 수는 1(누적합) + 1 이 나와야한다.
     * 만약 1,3 이라면 -> 정답은 2 ( (1(누적합)+ 1 ) 이 된다.
     *
     * 주어진 추의 무게가 1,2,4 라면, 이 때는 정답이 뭐가 될까?
     * 만들 수 있는 수 -> 1,2,3,4,5,6,7(누적합)
     * 따라서 이 때 정답은 8 ( 7(누적합) +1 ) 이 된다.
     *
     * */
    // 순차적으로 누적합을 구한다.
    public static int solve(){
        // 첫 번째 원소가 1이아닌 경우
        if(input[0] != 1) return 1;
        int sum = 0;
        for(int i = 0 ; i < n ;i++){
            if(input[i] > sum +1 ) return sum+1;
            sum += input[i];
        }
        return sum+1;
    }

    public static void main(String[] args) throws IOException{
        setting();
        System.out.println(solve());
    }
}