첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무게를 나타내는 N개의 양의 정수가 빈칸을 사이에 두고 주어진다. 각 추의 무게는 1이상 1,000,000 이하이다.
출력
첫째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다.
입력 예시
7
3 1 6 2 7 30 1
출력 예시
21
풀이
어떻게 접근할 지 몰라서 엄청 헤멨었는데, 풀이 중 자연스럽게 깨닫게 되었던 것 같다. 이런 문제가 참 재밌긴 하다.
(모든 풀이는 저울추 리스트가 오름차순 정렬되었음을 전제로 한다.)
n번째 저울추의 무게가 a_n이고, 1번째 저울추부터 n번째 저울추까지 사용했을 때 나타낼 수 없는 무게 최솟값을 min_n이라고 두자. min_n의 최댓값은 (1번부터 n번까지의 합) + 1이 된다. 모든 저울을 사용했을 때의 합보다 큰 수는 나타낼 수 없기 때문이다. 우리는 주어진 추들로 측정할 수 없는 양의 정수 무게의 최솟값을 알고 싶다. 따라서 이러한 범위의 연속성이 깨지는 첫 지점이 바로 정답이 되며, 연속성이 깨지지 않았다면 바로 그 (1번부터 n번까지의 합) + 1이 정답이 될 것이다.
여기서 귀납적으로 접근해보자. n-1번째까지의 저울추 집합이 1부터 sum([a_1 : a_(n-1)])까지 전부 나타낼 수 있다면, 새로운 n번째 저울을 포함시켰을 때, a_n을 사용하지 않을 경우와 사용할 경우 두 가지가 생긴다.
a_n을 사용하지 않을 경우 : n-1까지 사용했을 때의 저울추 집합은 [1, sum([ a_1 : a_(n-1) ])]의 범위를 나타낼 수 있다.
a_n을 사용할 경우 : a_n을 무조건 사용할 때를 가정하면, 위 범위에 단순히 a_n을 더하여 [a_n + 1 : sum([ a_1 : a_n ])]의 범위로 나타낼 수 있다.
범위의 연속성이 깨지는 조건은 위의 두 범위의 교집합이 존재하지 않을 때, 즉 sum([ a_1 : a_(n-1) ]) < a_n + 1 이 되는 시점이다!
따라서 O(N)의 시간 안에, 누적합을 구하며 위 조건 여부를 검사하는 방식으로 문제를 풀이할 수 있다.
풀이 코드(첫번째)
N = int(input())
weight_list = list(map(int, input().split()))
weight_list.sort(reverse = True)
MAX = sum(weight_list) + 1
cnt = 1
used_q = [0]
flg = True
prev = 0
while weight_list and flg:
length = len(used_q)
num = weight_list.pop()
if used_q[-1] < num :
used_q.append(num)
for i in range(length) :
if used_q[-1] < used_q[i] + num :
used_q.append(used_q[i] + num)
for i in range(cnt, len(used_q)) :
if used_q[i] != i :
flg = False
break
cnt += 1
print(MAX if flg else cnt)
풀이 코드(두번째)
N = int(input())
weight_list = list(map(int, input().split()))
weight_list.sort()
answer = 0
for weight in weight_list :
if answer + 1 < weight :
break
answer += weight
print(answer + 1)
