항해99 31일차 TIL( 저울 /백준)

문제         

레벨: G2
알고리즘: 그리디 
풀이시간: 1시간
힌트 참조 유무: 유

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

 

1 번째 시도   

• 완전탐색으로 찾기에는 2의 n승을 찾아야 하기 때문에 시간복잡도에 걸려 불가하다.
• 규칙을 찾아야 한다.
• 1부터 오름차순으로 탐색한다.
• 타겟넘버와 같거나 작은 숫자 중 가장 큰 숫자를 찾아 타겟넘버에서 뺀다. 이 과정을 반복한다.  
• 타겟넘버와 같거나 작은 숫자 중 가장 큰 숫자(는 저장한다.(나중에 써먹야 하기 때문에)
  • ex) 타겟넘버 9를 찾아야 한다.
  • 타겟넘버와 같거나 작은 숫자 중 가장 큰 숫자는 7이다.
  • 9-7 = 2 
  • 타겟넘버 2로 업데이트
  • 겟넘버와 같거나 작은 숫자 중 가장 큰 숫자는 2이다.
  • 2 - 2 = 0 이기 때문에 
  • 다음 타겟넘버 10으로 넘어간다.
  • 타겟넘버와 같거나 작은 숫자 중 가장 큰 숫자는 7이다.
  • 10-7=3
  • 타겟넘버 3으로 업데이트
  • 타겟넘버와 같거나 작은 숫자 중 가장 큰 숫자는 3이다.
  • 3 - 3=0이기 때문에
  • 다음 타겟넘버11으로 넘어간다.
  • 이 과정 실패할 때까지 반복

 

시간 내에 구현하지 못해 코드를 첨부하지 않겠습니다.
다른 분의 코드를 보며 공부해보겠습니다

2 번째 시도  

• 위에 설명이 너무 장황하고 정리가 안되어있지만 위 설명들을 뜻하는 단어가 있습니다. 바로 누적합입니다.

예제 1

입력 : 주어진 저울추
1 1 3 7 8

출력 : 측정할 수 없는 최솟값
6

간단하게 설명하기 위해 저울추를 오름차순으로 정렬한 값으로 시작하겠습니다.

저울추의 총 합을 재는 변수는 sum이라 하겠습니다. sum의 초기값은 0이며 이제 저울추를 하나씩 올려보며 주어진 저울추로 무게는 측정할 수 있는지 검사합니다.

 

sum 상태 = 0
첫 번째로, 무게가 1인 저울추는 sum + 1보다 크지 않기 때문에 무게 1까지는 측정할 수 있는 무게입니다. 따라서 sum에 첫 번째 저울추의 무게(1)를 더해줍니다. 여기서 살펴보아야 할 점은 sum이 나타내는 건 sum까지 무게를 측정할 수 있다는 의미라는 겁니다. 다음 단계를 확인할 수록 이해하기 수월해집니다.

 

sum 상태 = 1
두 번째로, 무게가 1인 저울추는 sum + 1보다 크지 않기 때문에 무게 2까지는 측정할 수 있는 무게 입니다. 따라서 sum에 두 번째 저울추의 무게(1)를 더해줍니다. 여기까지 보면 무게 1은 무게추 1개로 만들 수 있으며, 무게 2는 무게추 2개로 만들 수 있습니다.

 

sum 상태 = 2
세 번째로, 무게가 3인 저울추는 sum + 1보다 크지 않기 때문에 무게 3까지는 측정할 수 있는 무게 입니다. 따라서 sum에 세번째 저울추의 무게(3)을 더해줍니다.

 

sum 상태 = 5
네 번재로, 무게가 7인 저울추는 sum + 1보다 크기 때문에 sum + 1의 무게는 측정할 수 없습니다. 왜냐하면 지금까지 sum의 상태가 5기 때문에 무게 5까지는 측정할 수 있습니다. 다음으로 무게6을 재야 하지만 무게 7이 들어오면 더 이상 무게 6을 잴 수 있는 방법이 없기 때문입니다. 따라서 문제의 답은 sum + 1인 6이 됩니다.

 

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] weight = new int[n];

        for (int i=0; i<n; i++) {
            weight[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(weight);

        int sum = 0;
        for (int i=0; i<n; i++) {
            if (sum + 1 < weight[i]) {
                break;
            }

            sum += weight[i];
        }

        System.out.println(sum + 1);
    }
}