측정할 수 없는 최소 무게

오늘은 그리디(Greedy) 알고리즘의 핵심 개념을 활용하는 문제인 백준 2437번: 저울을 풀어보았다.

🧩 문제 요약

여러 개의 저울추가 주어진다. 이 추들을 이용해 측정할 수 없는 가장 작은 양의 정수 무게를 구하는 문제다.
예: [3, 1, 6, 2, 7, 30, 1] → 정답: 21

🔍 핵심 아이디어

• 추들을 오름차순 정렬한 후,
• 지금까지 만들 수 있는 최대 누적합을 `target`이라 한다.
• 매번 다음 추의 무게 `w`를 확인하며,
• w > target일 경우, 그 순간 target이 측정할 수 없는 최소 무게가 된다.

🤔 왜 그렇게 되는가?

예를 들어, 현재까지 1 ~ 20까지는 만들 수 있었다고 하자.
그런데 다음 추의 무게가 30이라면?
21~29는 만들 수 있는 방법이 존재하지 않기 때문에, 정답은 21이 된다.

작은 값들로 연속된 무게를 만들고 있는 중인데,
그 다음 추가 그 연속 범위보다 커버리면 구멍이 생기는 것!

🧠 한 줄 요약

작은 값부터 누적합으로 연속된 무게를 확장하다가, 그 다음 값이 gap을 만들면 그 지점이 답!

💻 Python 코드

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

target = 1

for w in weights:
    if w > target:
        break
    target += w

print(target)

📈 시간 복잡도

• 정렬: O(n log n)
• 탐색: O(n)
• 전체: O(n log n)

✅ 결론

단순 누적이 아니라, 연속된 범위를 이어나갈 수 있는지 체크하는 게 포인트.
그리디 알고리즘이 직관적으로 보일 땐 바로 이 문제처럼 깨끗하게 떨어진다!