프로그래머스 - 저울

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

 

문제 내용

하나의 양팔 저울로 물건의 무게를 측정하려 한다. 저울의 한 쪽에는 저울 추를, 다른 쪽에는 무게를 측정하려는 물건을 올린다. weight 배열에는 무게 추의 무게에 대한 정보가 들어있다.
이 추들로 측정할 수 없는 무게의 최소값을 구하자.

 

제한 사항

• 1 <= 저울 추 개수 <= 10,000
• 1 <= 추의 무게 <= 1,000,000

 

1. 정렬하기 - O(NlogN)

 

측정할 수 없는 무게의 최소값을 구해야 한다.
1부터 차근차근 구할 수 있는지 없는지 확인해보자.

적은 무게를 구하려면 무게가 적은 추를 사용해야 한다.
무게 7짜리로는 무게 2를 잴 수 없다.
따라서, 적은 무게의 추 부터 차례대로 사용해 나가면서 구할 수 없는 최소 무게를 찾아보자.

추의 무게는 정렬되지 않은 상태로 주어진다. 따라서 정렬을 하면 적은 무게의 추 부터 사용해볼 수 있다.

추의 무게들이 다음과 같이 주어졌다고 생각해보자.

[10,1,4,2]

정렬하면 다음과 같다.

[1,2,4,10]

그러면 무게 1부터 측정이 가능한지 차근차근 확인해보자.

무게 1은 1을 사용해서 측정할 수 있다.
무게 2는 2를 사용해서 측정할 수 있다.
무게 3은 1,2를 사용해서 측정할 수 있다.
무게 4는 4를 사용해서 측정할 수 있다.
무게 5는 1,4를 사용해서 측정할 수 있다.
무게 6은 2,4를 사용해서 측정할 수 있다.
무게 7은 1,2,4를 사용해서 측정할 수 있다.

무게 8은 무슨 수를 써도 측정할 수 없다.
1,2,4를 모두 써도 7까지만 측정이 가능하다.
그렇다고 10을 쓰자니, 10부터 측정이 가능하다.
7과 10 사이의 무게, 8과 9를 측정할 수 없다.

가만 살펴보니, 정렬된 배열의 왼쪽에서 부터 차례대로 더해나간 수 + 1이 다음 원소보다 작을 때, 지금 까지의 원소의 합 + 1이 측정할 수 없는 최소 무게인 것 처럼 보인다.

1이 있을 때, 1까지 측정이 가능하다. 1과 2가 있을 때, 1+2=3까지 측정이 가능하다. 1과 2와 4가 있을 때, 1+2+4=7까지 측정이 가능하다.

만약 10짜리 무게추가 8짜리였다면, 8짜리 하나만을 사용하여 무게 8을 표현할 수 있을 것이다. 그리고 9부터는 다시 기존의 무게추들을 이용하여 9보다 큰 무게를 표현할 수 있을 것이다. 10짜리 무게추가 8짜리 무게추가 된다면 어떻게 될 지 생각해보자.

8은 8을 사용하여 측정할 수 있을 것이다.
9는 8, “1“을 사용하여 측정할 수 있을 것이다.
10은 8, “2“를 사용하여 측정할 수 있을 것이다.
11은 8, “1,2“를 사용하여 측정할 수 있을 것이다.
12는 8, “4“를 사용하여 측정할 수 있을 것이다.
…
15는 8, “1,2,4“를 사용하여 측정할 수 있을 것이다.
16은 무슨 수를 써도 측정이 불가능하다. 1,2,4,8 모두를 더해도 15까지밖에 되지 않는다.

즉, 지금까지 더해 온 무게 추가 무게 추의 총 합을 모두 표현할 수 있다면, 다음으로 무거운 무게추가, 지금까지의 무게 추의 총 합 + 1 이하가 된다면
무게 추의 총 합 + 다음 무게 추의 무게
까지 측정할 수 있게 될 수 있다는 사실을 알 수 있다.

처음에는 무게의 총 합은 0이므로, 다음으로 필요한 무게 추는 1이다.
1이 있다면, 그 다음으로는 1 + 1 = 2 이하의 무게 추가 필요하다.
2가 있다면, 그 다음으로는 1 + 2 + 1 = 4 이하의 무게 추가 필요하다.
만약 2가 아닌 1이 있었다면, 그 다음으로는 1 + 1 + 1 = 3 이하의 무게 추가 필요할 것이다.

무게 추를 오름차순으로 정렬한 뒤, 현재 무게 추의 총 합에 1을 더한 값이 다음 무게 추의 무게보다 적다면, 현재 무게 추의 총 합에 1을 더한 값이 구할 수 없는 최소 무게가 될 것이다.

그러면 이 과정을 코드로 표현해보자.

 

solution.cpp

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> weight) {
    sort(weight.begin(), weight.end());
    int next = 1;
    
    for (int v : weight)
    {
        if (v > next)   return next;
        next += v;
    }
    
    return next;
}

 

이 문제는 짧은 코드로 풀리는 문제이다.
코드의 양만 보고는 굉장히 쉬운 문제라고 생각할 수 있다.

하지만 코드의 길이는 난이도를 의미하지 않는다. 코드를 이끌어 내는 것은 논리의 영역이다. 이 코드로 정답을 이끌어 낼 수 있음을 증명하고 써야 한다.
그렇다고 반드시 본인이 증명할 필요는 없다. 누군가가 증명한 것을 본인이 이해하고 쓰는 것도 중요하다.