문제
하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.
무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.
예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다.
입력
첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무게를 나타내는 N개의 양의 정수가 빈칸을 사이에 두고 주어진다. 각 추의 무게는 1이상 1,000,000 이하이다.
출력
첫째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다.
예제 입력 1
7
3 1 6 2 7 30 1
예제 출력 1
21
문제 해결 과정
결론만 얘기하면 사실 도저히 해결 방법이 생각나지 않아 블로그를 참고했다.
처음에는 DP로도 시도를 했고, heapq를 시도하려고 했다.
마땅한 해결 방법이 생각나지 않아 해결하지 못했다.
그러다가 정말 기가 막힌 풀이 방법을 알게 되었다.
일단 주어진 숫자들을 이용해서 합을 구할 때, 1~K까지의 값을 구한다고 가정을 해보자.
K는 주어진 숫자들을 모두 다 합한 것일 것이다.
예를 들어, [1, 1, 2]가 있다고 가정하면 1부터 4까지의 값을 구할 수 있다.
그 다음 숫자로 5가 있다고 가정하면, 그다음은 5, 6, 7, 8, 9를 구할 수 있는 것이다.
결론적으로 측정할 수 없는 양의 정수 무게 중에 가장 작은 것을 구하려면 1부터 값을 더해서 해당 인덱스의 값보다 작게 된다면 그 때의 값이 정답이다.
최종 코드
import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
target = 1
for num in arr:
if target < num:
break
target += num
print(target)참고 블로그
