백준 2437번 파이썬 문제풀이(저울)

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

2437번: 저울

---

아이디어 구상하는것이 처음에 되게 까다로웠다. 몇번의 케이스를 직접 쓰다보니 다음과 같은 정보를 얻을 수 있었다.

 

만약 

해당 i번째의 값보다 그 앞 i - 1번째까지의 합 + 1 것보다 작거나같다면 무조건 i번째까지 합한 값은 무조건 측정이 가능하다는 것이다. 즉, 1 2 3 8 가있을때,  첫번째 1 보다 2번째 2가 1+ 1와 같기 때문에 총 합인 3까지는 무조건 측정이 가능하다는것이다. 그럼 3번째 3을 기준으로 1 + 2 가 3과 같기 때문에 6까지는 어떠한 수든 측정이 가능하다. 그러나 1 + 2 + 3 +1 한 7보다 네번째 8이 크기때문에 여기서 7은 어떻게 해도 측정할 수가 없다. 따라서 7이 정답이다. 

 

이런식으로 아이디어를 짰고 한가지 더 생각을 해야한다. 만약에 4 5 6 이면 답은 1이 되어야한다. 그래서 초기누적합을 0 으로 설정해주고 배열의 첫번째 항부터 크기비교를 하면 쉽게 구할 수 있다.

 

N = int(input())
arr = list(map(int, input().split()))

arr.sort()

sum_ = 0  # 누적합을 저장
for i in range(N):

    if arr[i] > sum_ + 1:  # 만약 해당 i번째의 값이 그전누적합 + 1 보다 크다면
        print(sum_ + 1)  # 누적합 + 1 을 출력후 종료
        exit()
    sum_ += arr[i]  # 그렇지 않으면 계속 누적합을 구해준다.

print(sum_ + 1)  # 위의 if에 걸리지 않았다면 모두 더한 값 + 1이 정답