[프로그래머스 탐욕법]저울 - Python3

문제

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

 

알고리즘

def solution(weights):
    weights.sort()
    temp = weights[0]
    for i in range(1, len(weights)):
        if weights[i] - temp > 1:
            break
        else:
            temp += weights[i]
    
    return temp + 1
    
weights = [3, 1, 6, 2, 7, 30, 1]
print("정답: ", sol5(weights))

설명

코드는 짧지만, 이 코드를 짜기 위한 내 노력은 정말 어마어마했다. 

핵심 아이디어는, 일단 추를 오름차순으로 정렬한 후에 가장 무게가 낮은 추 부터 부분합을 계산하는 것이다. 

예를 들어, weights = [3, 1, 6, 2, 7, 30, 1]이라 하자. 이 배열을 정렬하면 [1, 1, 2, 3, 6, 7, 30]이 된다.

0번째 추부터 찬찬히 들여다보자. 0번째 원소는 1이다. 그렇다는 것은, 1만큼은 만들 수 있다는 것이다.

1번째 추를 보자. 역시 1이다. 그렇다는 것은, 1, 2는 만들 수 있다는 것이다. 지금까지의 추들의 부분합은 2이다. 

2번째 추를 보자. 2이다. 즉, 1, 2, 3, 4 는 만들 수 있다는 것이다. 지금까지의 추들의 부분합은 4이다. 

3번째 추를 보자. 3이다. 그럼 1, 2, 3 ,4에 이어서 5, 6, 7을 만들 수 있다. 추들의 부분합은 7이다. 

4번째 추는 6이다. 그럼, 1, 2, 3, 4, 5, 6, 7에 이어서 8, 9, 10, 11, 12, 13을 만들 수 있다. 추들의 부분합은 13이다. 

5번째 추는 7이다. 그럼, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13에 이어서, 14, 15, 16, 17, 18, 19, 20까지 만들 수 있다. 부분합은 20이다. 

6번째 추는 30이다. 근데, 0번째부터 5번째까지의 수로 20까지 만들 수 있었는데, 여기서 갑자기 30을 더해버린다면, 우리는 21을 만들 수가 없다. 

바로 여기에 주목해야 한다. 위의 6번째 원소를 살펴봄에 있어서, 0번째부터 5번째의 합이 20이었다. 그런데 그 다음에 나타나는 추의 무게가 21보다 큰 수가 나타난다면, 우리는 그 21을 만들 수가 없는 것이다. 왜냐하면 5번째 원소를 몽땅 다 써서 만든 최대의 값이 20이므로, 21을 만드려면 21만이 나와야 한다. 그러나 21이 나오지 않고, 21보다 큰 30이 나왔기 때문에, 우리는 21을 절대 만들 수 없다.

뭔가 느낌을 좀 잘 받으라고, 주어진 추로 만들 수 있는 최대의 값과, 추들의 부분합을 배경을 칠해놓았다. 

아무튼 이 사실을 좀 일반화를 해보자면, i번째까지 추들의 합을 누적해서 더한 값을 sum이라 할 때, i+1번째 원소가 sum +1 보다 크다면, 우리는 그 sum +1을 주어진 추로는 만들 수 없다. 그것을 고려해서 적은 것이 위 알고리즘이다. 

 

결과

올바른 결과를 출력한다.

후기