오늘 알고리즘을 푸는데 참 기묘한 문제를 풀었다.
https://www.acmicpc.net/problem/2437
문제
하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.
무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.
예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다.
입력
첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무게를 나타내는 N개의 양의 정수가 빈칸을 사이에 두고 주어진다. 각 추의 무게는 1이상 1,000,000 이하이다.
출력
첫째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다.
바로 저울문제라는건데, 주어진 추를 가지고 만들지 못하는 제일 작은 수를 구하는 문제이다. 문제를 풀고도 한동안 어이가 없었던 기분이 든다.
먼저 이해를 하기 쉽게 2진수를 생각해보자.
lst = [0,0,0,0,0,0]위와 같이 6자리의 2진수 숫자가 있다면 우리는 1초의 망설임도 없이 0~63까지의 숫자를 만들수 있다고 말할 수 있다.
그럼 2의 배수가 아닌 수들은?
여기서 뇌정지가 오는거다.
얼핏 생각하면 안될거같은데 안될 이유가 없는것이다.
그래서 한번 예제로 계산해보자.
lst = [1]
1 = 1
lst = [1,1]
1 = 1
2 = 1+1
lst = [1,1,2]
1 = 1
2 = 1+1
3 = 1+2
4 = 1+1+2
lst = [1,1,2,3]
1 = 1
2 = 1+1
3 = 1+2
4 = 1+1+2
5 = 1+1+3
6 = 1+2+3
7 = 1+1+2+3
lst = [1,1,2,3,9]
1 = 1
2 = 1+1
3 = 1+2
4 = 1+1+2
5 = 1+1+3
6 = 1+2+3
7 = 1+1+2+3
8 = ?????위와 같은 결과가 나왔다.
결과를 잘 보면 금방 눈치챌 수 있는것은
list에서 n이 추가될때, sum(list)+1 이하의 수가 추가된다면 만들 수 있는 숫자에 공백이 생기지 않는다는 것이다.
(만약에 7까지 만들수 있고 8이 추가된다면 숫자의 공백이 없다.)
그래서 마지막에 9가 추가될때
1+1+2+3 < 9가 되기 때문에
8을 만들 수 없어서 만들지 못하는 숫자가 생긴다는 것이다.
풀이 코드는 다음과 같다.
N = int(input())
arr = list(map(int,input().split()))
arr.sort()
ans = 1
for i in arr:
if ans < i:
break
ans += i
print(ans)어이없을정도로 짧게 나온다.
