저울 Pgs#43163

저울 PGs#42886

Python 코드 보기

def solution(weight):
    weight.sort()
    answer = 0
    
    print(weight)
    for item in weight:
        if item <= answer+1:
            answer += item
        else:
            break
        
    return answer+1

---

☝ 입력 형식

• 저울추가 담긴 배열 weight가 매개변수로 주어집니다.

🤞 출력 형식

• 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 return 하도록 solution 함수를 작성해주세요.

🤟 구현 과정

1. 알고리즘 정립

이 문제를 풀기 위한 최대 난관은 최대 무게를 구하는 방법을 찾는 것이다.

저울추들을 무게 별로 나열했을 때 n번째 까지의 저울추로 만들 수 있는 무게 중 최대 값을 K(n)이라고 하자.

만약 n번째 저울추까지 이용하여 n번째 까지 저울추의 무게의 합이 되는 무게를 모두 만들 수 있다면, 즉 K(n) = $\sum_{k=1}^n {k}$ 인 동안, n+1번째 저울추의 무게가 K(n)+1보다 작거나 같을 때!

n+1개의 저울추를 이용해서 K(n)+(n+1번째 저울추의 무게) 까지 무게도 만들 수 있다.

말로 하니 복잡하다. 문제의 입출력 예를 예시로 들어보자.

2. 입출력 예를 통한 예시

weight	weight.sort()	return
[3, 1, 6, 2, 7, 30, 1]	[1,1,2,3,6,7,30]	21

이 때, K(n)을 알아보자.

n	weight[n]	K(n)	해설
0	1	1	1까지 무게 측정 가능
1	1	2	1<=1~K(0)~+1이므로, 1~K(0)~+1까지 모든 무게 측정 가능
2	2	4	2<=2~K(1)~+1이므로, 2~K(1)~+2까지 모든 무게 측정 가능
3	3	7	3<=4~K(2)~+1이므로, 4~K(2)~+3까지 모든 무게 측정 가능
4	6	13	6<=7~K(3)~+1이므로, 7~K(3)~+6까지 모든 무게 측정 가능
5	7	20	7<=13~K(4)~+1이므로, 13~K(4)~+7까지 모든 무게 측정 가능
6	30	20	30<=20~K(5)~+1이 아니므로, 21부터는 측정 불가능.

위의 표를 읽어보면 1번의 설명이 쉽게 이해 될 것이다.

이런 방식을 통해, 입출력 예시의 답도 21이 나온다.

3. 코딩하기

weight를 오름차순으로 정렬한 뒤, 0번째 원소부터 answer에 계속 더해준다.

answer+1이 weight의 다음 원소보다 작을 때, answer+1을 return하면 된다.