<정렬> 2437번 저울 with 파이썬

 

문제

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

 무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.

 

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

입력

첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무게를 나타내는 N개의 양의 정수가 빈칸을 사이에 두고 주어진다. 각 추의 무게는 1이상 1,000,000 이하이다.

출력

첫째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다.

정답비율

37.618%

알고리즘 분류

 #정렬 #그리디 #그리디알고리즘 #배열

 

 

import sys
input = sys.stdin.readline

n = int(input())
lst = list(map(int, input().split()))
lst.sort()
answer = sum(lst) + 1
result = 0
for i in lst:
    if result + 1 < i:
        answer = result + 1
        break
    else :
        result += i
print(answer)

 

 - 처음에는 마땅히 생각나는 방법이 없어서 단순하게 문제에서 원하는대로 일단 풀었다. 조합을 이용하여 1부터 n개를 뽑았을 때 나올 수 있는 모든 합을 배열에 담은 후 정렬시켰다. 그 후 1부터 올라가며 비교하여 숫자가 없으면 출력했다. 당연히 시간초과가 났다. 조합은 시간복잡도가 O(n!) 이다. n이 11이기만 하더라도 약 4천만의 연산을 수행한다.

 

 - 따라서 다른방법을 찾아보았다. 먼저 입력 받은 배열을 정렬시킨다. 앞에서부터 순서대로 더해가는데 이때, 누적된 값+1 보다 다음에 나온 숫자가 더 크다면 누적된 값+1을 절대 나올 수 없는 값이다.

 

 - 예를 들어 1 2 3 8을 보자. 첫 누적값은 1이다. 이보다 1큰 2보다 다음숫자인 2는 크지않다. 마찬가지로 누적값 3에 1을 더한 값보다 셋째 값 3은 크지 않다. 이는 셋째 값까지를 이용하면 어떻게든 4를 만들 수 있다는 의미이다. 이제 누적값은 6이 되었다. 이보다 1이 큰 7보다 다음값인 8이 더 크다. 이는 7을 절대 만들 수 없게되는 것이다. 앞의 숫자들을 아무리 합해봤자 최대 6인데도불구하고 다음 숫자는 8이다. 

 

 - 사실 글로 쓰느라 조금 복잡하게 느껴지지만 직접 써보면 금방 이해된다. 정렬된 배열이기에 가능하다.

 

 

---

 

참고

2437번: 저울