[백준 알고리즘] 2437번: 저울 (Python)
https://www.acmicpc.net/problem/2437
2437번: 저울
하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓
www.acmicpc.net
소스코드
풀이
★ 처음 생각했던 방식은 최솟값을 구해야 하기에 입력 받은 저울 추를 오름차순 정렬하고, 저울추로 구할 수 있는 모든 경우의 수를 구한 뒤, 구하지 못하는 값들 중 최솟값을 출력하는 방식이었습니다 !
ex) [A,B,C] => A, A+B, A+C, B+C, A+B+C
하지만 당연하게도 시간초과가 발생했고, 입력 받은 예제를 토대로 위와 같은 방식을 출력해보니 다음과 같은 결과를 얻을 수 있었습니다.
ex) [3,1,6,2,7,30,1]을 내림차순 정렬 => [1,1,2,3,6,7,30]
위의 값을 제가 한 방식대로 출력하면
[1]
[1,2]
[1,2,3,4,]
[1,2,3,4,5,6,7]
[1,2,3,4,5,6,7,8,9,10,11,12,13]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20, 30,31,32 ...]
=> 21부터는 만들지 못함
즉, 저울 추를 하나씩 합한 값을 기준으로 그 밑의 값들은 다 만들 수 있었습니다.
이는 저울추를 요소로 반복문을 돌았을 때, 그 전까지의 저울추를 모두 합한 값보다 해당 저울 추의 값이 크다면, 저울 추의 합에 +1한 값이 만들 수 없는 최솟값이 됩니다.
★ ans가 1부터 시작하는 이유는 만들 수 없는 최솟값 중 가장 작은 값이 1이기 때문입니다.