문제 설명

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

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

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

문제 접근 방식

문제의 풀이 자체는 아주 짧지만 오래 고민하고 푼 문제입니다.. 😅

처음에는 weight를 모두 더해서 나오는 값까지 check 배열을 생성해서 brute-force + 조합으로 풀려고 했으나 검사해야할 최대 범위가 너무 커서 올바른 접근 방식이 아님을 판단했습니다.

먼저, 최소 측정 무게를 구하기 위해 weight를 오름차순으로 정렬 시켜야합니다.
[1, 1, 2, 3, 6, 7, 30]

1번째 추의 무게는 1입니다. 즉, 1만큼의 무게는 측정이 가능합니다.
현재, 추의 부분합은 1입니다.

2번째 추의 무게는 1입니다. 즉, 1, 2(1+1)의 무게 측정이 가능합니다.
현재, 추의 부분합은 2입니다.

3번째 추의 무게는 2입니다. 즉, 1, 2에 이어서 추가로 3(1+2), 4(2+2)무게 측정이 가능합니다.
현재, 추의 부분합은 4입니다.

…

6번째 추의 무게는 7입니다. 그럼 이전 값들 1, 2, 3 ,4 , ... , 12, 13에 추가로 최대 20까지 무게 측정이 가능합니다.
현재, 추의 부분합은 20입니다.

7번째 추의 무게는 30입니다.
하지만, 해당 추를 추가한 최소 무게는 31(1+30)가 됩니다.
이는 이전 최대 측정 값 20의 무게를 뛰어넘는 값이 되어 7번째부터는 측정이 불가능해집니다.

따라서, 다음과 같이 문제를 풀 수 있습니다.

풀이 코드

def solution(weight):
    weight.sort() # 작은 무게부터 더하면서 접근해야하므로

    subtotal = 1 # 추의 최소 무게는 1
    for w in weight:
        if subtotal < w: break
        subtotal += w

    return subtotal