[백준] 2437 저울

✔️ 문제 링크

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

💡 핵심 아이디어

탐욕문제는 아이디어 싸움이라서 어렵다...
처음에는 combination으로 부르트포스 방식으로 접근하였다가 실패
탐욕적인 방법으로 풀은 과정은 다음과 같다.

1️⃣ 숫자들을 list로 관리 후 오름 차순으로 정렬

2️⃣ list를 순회하면서 이전 숫자까지의 누적 합을 구한 수의 + 1값이 현재 값보다 큰지 판별 => 만약 현재 순회하고 있는 수가 더 크면 이전 누적합 + 1의 값이 답이 되게 된다.

❗️ 이 방법이 처음에는 생각하기 어려운데 예시를 들어보면
현재 1 1 2 3 6 7 30 의 수가 있다 생각하고 2까지 누적 합을 구했다고 하자.(누적합은 4)

이제 3을 고려해볼 차례인데 누적합인 4와 더해주면 7이 되고 4와 7의 사이의 수는 5(차이 1),6(차이 2)이다. 이때, 누적합인 4범위 내에서 모든 조합의 수를 만들어 줄 수 있다 하였으니 7 -1 = 6, 7- 2 = 5를 만들어 줄 수 있다!

만약, 3이 아닌 누적합 + 2인 수인 6이라고 가정하면 누적합 + 6 = 10인데 이렇게 되면 5,6,7,8,9의 수를 만들 수 있냐 판단을 해야 하는데 10 - 1 = 9, ... , 10 - 4 = 6 까지의 수를 만들 수는 있으나 5는 만들수가 없음으로 더이산 연속된 수를 만들 수 없다고 판단 할 수 있다.

3️⃣ 만약, 하나의 추만 있고 1이 아닌 숫자라면 답은 1인 예외 처리를 해 준다.

⭐️ 소스코드

if __name__ == '__main__':
    N = int(input())
    num_list = list(map(int,input().split()))
    ans = -1
    if 1 not in num_list:
        ans = 1
    else:
        num_list.sort()
        temp_sum = num_list[0]
        for i in range(1, len(num_list)):
            n = num_list[i]
            if (temp_sum + 1) < n:
                ans = temp_sum + 1
                break
            temp_sum += n

    if ans == -1:
        print(sum(num_list) + 1)
    else:
        print(ans)