BOJ 2437 : 저울 (Python)

문제

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

2437번: 저울

 

 

코드

import sys
input = sys.stdin.readline

n = int(input())
array= list(map(int, input.split()))
array.sort()

target = 1

for i in array:
    if target < i:
        break

    target += i

print(target)

 

 

풀이

target 이라는 변수에 오름차순으로 정렬한 저울추들을 차례대로 더한다. 이때 target이 해당 저울추보다 작은 경우에는 반복문을 종료한다. 왜냐하면 target이 해당 저울추보다 작으면 그 사이에 무게를 잴 수 없는 숫자가 만들어지기 때문이다.

 

target의 초기 값은 1이다. → 만약 가장 가벼운 저울추가 1이 아니라면 무게가 1인 경우는 무조건 잴 수 없기 때문에 1이 가장 작은 측정할 수 없는 무게가 되기 때문이다.

 

if target < i:
        break

그래서 반복문 첫번째부터 이 if문에 걸리기 때문에 반복문이 종료되고 정답은 target의 초기 값인 1이 된다. 

 

그 외에는 위에서 설명한 방법대로 진행된다. 

 

 

 

---

 

기타

처음에는 저울추들의 총합에서 가장 큰 저울추의 무게부터 차례대로 빼면서 측정할 수 없는 무게를 찾으려고 했는데 당연하지만 시간초과가 났다. 냅다 구현하려고 하기보다는 쉬운 방법을 생각해내는데 더 시간을 많이 쏟아 부어야 할 것 같다.

 

시간초과가 난 코드

import sys
input = sys.stdin.readline

n = int(input())
weight = list(map(int, input().split()))
weight.sort(reverse = True)

if weight.count(1)==len(weight):
    print(sum(weight)+1)
    sys.exit()

if weight[len(weight)-1] >= 2:
    print(weight[len(weight)-1]-1)
    sys.exit()

for i in range(1,sum(weight)):
    integer = i
    sub = 0
    for w in range(n):
        if weight[w] <= integer:
            if integer > sum(weight)-sub:
                print(i)
                sys.exit()
            
            integer -= weight[w]
        sub += weight[w]    
        if integer == 0:
            break

    if integer > 0:
        print(i)
        sys.exit()