[백준 알고리즘] 2437번: 저울 (Python)

https://www.acmicpc.net/problem/2437

2437번: 저울

 

소스코드

 

풀이

★ 처음 생각했던 방식은 최솟값을 구해야 하기에 입력 받은 저울 추를 오름차순 정렬하고, 저울추로 구할 수 있는 모든 경우의 수를 구한 뒤, 구하지 못하는 값들 중 최솟값을 출력하는 방식이었습니다 ! 

 

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이기 때문입니다.