[프로그래머스 level_3] 저울 for JAVA

https://programmers.co.kr/learn/courses/30/lessons/42886

프로그래머스

[문제 설명]

 

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 합니다. 이 저울의 양팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같습니다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있습니다.

저울추가 담긴 배열 weight가 매개변수로 주어질 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 return 하도록 solution 함수를 작성해주세요.

예를 들어, 무게가 각각 [3, 1, 6, 2, 7, 30, 1]인 7개의 저울추를 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21입니다.

 

제한 사항

• 저울추의 개수는 1개 이상 10,000개 이하입니다.
• 각 추의 무게는 1 이상 1,000,000 이하입니다.

입출력 예

weight	return
[3, 1, 6, 2, 7, 30, 1]	21

 

[풀이]

수학적 규칙을 사용했다. 어떤 연속되는 값이 있다고 가정하자(중복을 허용한다),  ex) 1,2,2,3이 있으면 1+2+2+3 = 8, 즉 1~8까지의 숫자를 표현할 수 있다. 좀 더 자세히 살펴보면 ex) 1,2,4는 연속되는 값이 아니지만 1+2 = 3이다. 그다음 오는 숫자는 4이므로 연속될 수 있다. 주의할 점은 3+4이 오면 1~7을 다 표현할 수 있는 것이 아니다. 1+2+4+8처럼 존재해야만 한다. 

 

[코드]

public int solution(int[] weight) {
        Arrays.sort(weight);
        int answer = weight[0];
        for(int i = 1; i < weight.length; i++) {
            if(answer+1 < weight[i]) {
                break;
            }else {
                answer += weight[i];
            }
        }
        return answer+1;
    }

 

느낀 점 : 처음에는 이진 탐색, DFS, 조합 다 시도해봤지만 터무니 없이 길어지는 코드를 보고 뒤집었다. 약간의 Searching을 통해 규칙을 알게 되었고, 보자마자 이해가 가지 않았지만 계속 보니 외워지기도 하고 이건 그냥 규칙으로 외우고 있어야겠구나라는 생각을 하게 되었다.

 

**피드백은 언제나 환영입니다.