백준 2437번 '저울' 알고리즘 설명

✨ Written with ChatGPT

문제 상황

백준 2437번 저울 문제를 풀었다.
한눈에 그리디로 풀면 되겠다는 건 알았는데, 구체적으로 감이 잘 안 잡혔다.

측정할 수 없는 양의 정수 무게라는 표현을 이해하는 데도 한 5분 걸린 것 같다.

풀이 설명

이 문제는 주어진 추들만으로 만들 수 없는 가장 작은 무게를 찾는 문제다.
추의 무게는 양의 정수이고, 모든 무게는 1개 씩만 사용 가능하다.

발상의 핵심은 지금까지 만들 수 있는 무게의 최대 범위(sum_weight)를 유지하면서,
그 다음 추의 무게가 그 범위를 초과하는지 아닌지를 체크하는 것이다.

1. 추 배열을 오름차순으로 정렬한다.
2. sum_weight를 0으로 초기화한다.
3. 추를 하나씩 순회하면서
   • 현재 추 무게가 sum_weight + 1보다 크다면(조건 A), sum_weight + 1이 측정할 수 없는 최소 무게가 된다.
   • 그렇지 않다면, sum_weight에 현재 추 무게를 더해서 만들 수 있는 무게 범위를 확장한다.
4. 순회가 끝나도 조건 A가 true였던 적이 없다면(각 구간의 누적합이 다음 추 무게 이하), 최종 sum_weight + 1이 정답이다.

• ex) 저울추 배열 [1, 2, 5, 10]
  • 1 → sum_weight = 1
  • 2 → sum_weight = 3
  • 5 → 5 > 3 + 1 → 측정할 수 없는 최소 무게는 4

제출한 코드

본래 결과를 저장하는 res 변수를 두고 마지막에 res만 출력하려고했는데,
그럴 필요 없이 sum_weight + 1을 바로 출력하고 return하는 방식이 더 깔끔했다.

def solution():
    N = int(input())
    weights = list(map(int, input().split()))
    weights.sort()

    sum_weight = 0
    for w in weights:
        if w > sum_weight + 1:
            print(sum_weight + 1)
            return
        sum_weight += w

    print(sum_weight + 1)

성능 비교

• 이 문제는 정렬 이후 한 번만 순회하면서 누적합을 관리하면 되기 때문에 그리디 알고리즘으로 매우 빠르게 풀 수 있다.

핵심 레슨런

• "현재까지 만들 수 있는 무게의 범위를 유지하면서 그 다음 추가 그 범위를 넘기는지를 확인한다"는 그리디 아이디어를 잘 기억해놔야겠다.
• 불필요한 변수 없이 조건이 만족되는 순간 바로 출력하는 방식이 더 깔끔하고 직관적일 수 있다.

결론

처음엔 막막했지만, 작은 예시를 통해 범위를 확장해가는 규칙을 직접 확인해보니 감이 잡혔다.
정렬 + 누적합을 활용한 전형적인 그리디 문제였고, 앞으로도 이런 유형을 만나면 "어떤 조건에서 break(return)를 하면 될지"를 잘 판단해야겠다고 느꼈다.