[백준] 2437. 저울 / 파이썬 (python)

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

2437번: 저울

---

문제 풀이 

문제를 관통하는 키워드는 '누적합'이다. 

예를 들어, 

아래와 같이 주어졌다고 가정해보자. 

 4
 1 2 4 5

가장 작은 추 하나만 가지고 있는 상태에서 하나씩 추가로 가지게 된다고 생각하면

1만 가지고 있을 때는 측정 가능범위 [0, 1]

2가 추가되면 [0, 1] + [2, 3] = [0, 3]

4가 추가되면 [0, 3] + [4, 7] = [0, 7]

5가 추가되면 [0, 7] + [5, 12] = [0, 12]

 

즉, "새로 추가된 추의 무게 <= 현재까지의 누적합" 이어야
0부터 공백 없이 누적합(새로 추가된 무게까지 포함)까지의 범위를 커버할 수 있는 것이다.

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

target = 1
for i in weights:
    if target < i:
        break
    else:
        tar += i
print(target)

 

아래와 같이 해도 결과값은 정상적으로 도출되었으나 제출 결과 '틀렸습니다'를 받았다.

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

acc = 0
if n == 1:
    if weights[0] >= 2:
        print(1)
    else:
        print(2)
else:       
    for i in range(n-1):
        acc += weights[i]
        if weights[i+1] <= acc:
            continue
        else:
            print(acc+1)