[자바/백준 골드2] #2437 저울

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

🔒 골드2 - #2437 저울

 

 

📌 테스트케이스 추가 힌트

7
1 1 1 3 5 13 16

= 12

3
1 2 3

= 7

1
1

= 2

2
2 2

= 1

 

 

✍️ 풀이법

 

처음에는 단순하게 추를 이용해서 1을 만들고, 2를 만들고, 3을 만들고 ... 이런 식으로 생각했었다.

하지만 추를 무게 순으로 정렬하더라도, 내가 원하는 답을 얻기 힘들다는 생각에 추가 테스트 코드를 만들어보며 좀 더 고민 해 보았다.

 

그 결과 내가 찾은 규칙은 다음과 같았다.

7
1 1 1 3 5 13 16

= 12

 

해당 테스트케이스에서 뒤에서부터 1보다 작거나 같은 값을 찾으면 세번째 (= index 2) 1에서 찾아지게 된다.

그 값의 이전 index 값들의 합은 만들 수 있다는 뜻이 된다. 위를 예시로 1+1+1 인 3까지는 만들 수 있다는 뜻이다.

따라서 그 다음 수인 4를 다시 뒤에서 부터 찾으면 3 (= index 3) 에서 멈추게 되고, 1+1+1+3 인 6까지 만들 수 있게 된다.

 

하지만 이러한 방식으로는 문제를 해결할 수 없었다. 

 

뒤에서부터 찾는 다는 것은 시간복잡도를 엄청 잡아먹기 때문이었다.

 

 

 

 

 

다음 방식은 앞서 설명한 방법을 앞에서 시작하는 방식으로 바꾼 방법이다.

 

역시나 가장 작은 수인 1부터 찾는다면, 맨 앞 (= index 0) 1에서 찾아지게 된다.

앞서 말한 방법과 같은 방법으로, 2보다 큰 수를 찾는다면 세 번째 (= index 2)에서 찾아지게 되고,

앞서 말한 방법으로 1+1+1인 3까지는 만들수 있다는 뜻이 된다.

 

따라서 다음은 4를 찾는다면 5 앞에서 멈추게 되고, 1+1+1+3 인 6까지, 그 다음은 1+1+1+3+5 인 11까지, 만들 수 있게 되는 방식이다. 다음 찾는 수인 12의 경우, 바로 다음 수가 13이기 때문에 만들 수 없어서 답은 12가 된다.

 

 

 

즉, 앞에서 부터 합을 구하고, 다음 수가 합의 다음 수보다 큰 수라면, 답을 구할 수 없게 된다는 것이다.

 

 

 

풀이법

    1. 추를 무게 순서대로 정렬한다.

    2. ( (i)번째 수 까지의 합 +1)이 (i+1)번째 수 보다 작다면, 해당 수는 만들 수 없다.

 

 

 

 

 

 

🗝️ 풀이

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class baekjoon2437 {

    private static List<Integer> weight = new ArrayList<>();
    static Long findNum = 0L;
    private static int findIndex = 0;


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        for (int testCase = 0; testCase < N; testCase++) {
            weight.add(sc.nextInt());
        }

        solve();
        System.out.println(findNum);
    }

    public static void solve() {
        Collections.sort(weight);
        findNumber();
    }

    private static void findNumber() {
        int sum = weight.get(0);

        if (weight.get(0) != 1) {
            findNum = 1L;
            return;
        }

        for (int i = 1; i < weight.size(); i++) {
            if (sum < weight.get(i)-1) {

                break;
            }
            sum += weight.get(i);
        }

        findNum = Long.valueOf(sum +1);
    }
}