[그리디] 코딩테스트 문제 TIL (저울) - 백준 2437번

오늘 문제는 제가 푼 백준 문제중 가장 티어가 높은 문제입니다. 살펴볼까요?

---

1. 오늘의 학습 키워드

• 그리디 알고리즘
• 정렬

---

2. 문제: 2437. 저울

• 단계: 🥇 골드 2단계
• 주제:
  • 그리디 알고리즘
  • 정렬
• 출처: https://www.acmicpc.net/problem/2437

문제

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.

예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다.

입력

첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무게를 나타내는 N개의 양의 정수가 빈칸을 사이에 두고 주어진다. 각 추의 무게는 1이상 1,000,000 이하이다.

출력

첫째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다.

예제 입력 1 복사

7
3 1 6 2 7 30 1

예제 출력 1 복사

21

---

3. 문제 풀이

Step1. 문제 이해하기

주어진 문제는 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 문제입니다.

뭔가 감이옵니다. 바로 저울추들을 오름차순으로 정렬하여 무게가 가벼운 추부터 더해가면서 가능한 무게를 측정하는것입니다.

입출력 조건을 보겠습니다.

• Input:
  • 첫째 줄에는 저울추의 개수가 주어집니다. 이것은 1이상 1000이하입니다.
  • 따라서 $O(n^2)$까지는 여유 있습니다.
  • 둘째 줄에는 저울추들의 무게가 주어집니다.
• Output:
  • 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력합니다.

Step2. 문제 분석하기

저울추를 오름차순으로 정렬된 순서대로 누적하면서 가능한 무게 범위를 확장하는 방식으로 접근하다가 불가능한 순간에 멈춘다면 최솟값을 구할수 있습니다.

예를 들어 무게 w를 측정할 수 있으려면, 현재까지 측정가능한 무게의 범위에서 w를 포함하여 확장할 수 있어야 합니다.

하지만 현재 무게 w가 측정 가능한 범위를 벗어난다면, 더 이상 확장이 불가능해지고, 이전까지의 결과가 측정할 수 없는 가장 작은 무게가 됩니다.

즉, 저울추를 오름차순으로 정렬하여, 가장 작은 값부터 시작해 가능한 무게 범위를 차례대로 확장하기 때문에 현재까지 측정 가능한 무게 범위에 영향을 주는 가장 작은 추부터 순차적으로 반영하게 됩니다.

따라서 이 과정은 문제를 해결하는 데 있어서 최적의 선택입니다. 그러므로 그리디 알고리즘 유형이라고 볼 수 있습니다.

그렇기 때문에 전체 저울추를 정렬하고 순회하기 때문에 $O(N \log N)$의 시간 복잡도로 구현이 가능한 것을 알 수 있습니다.

예제를 들어 더 확실하게 접근해보겠습니다.

현재 가능한 무게를 1kg출발하며 변수를 result로 지칭하겠습니다. 왜 1kg로 출발하나면 가능한 무게의 최댓값 + 1 은 가능하지 않은 무게 최솟값이기 때문에 미리 1kg부터 시작하여 나오는 값을 바로 반환하면 되기 때문입니다.

예제 풀이

입력

N = 7
weights = [3, 1, 6, 2, 7, 30, 1]

풀이 과정

1. 정렬: [1, 1, 2, 3, 6, 7, 30]
2. 초기 상태:
   • 측정 가능한 범위: [1, result-1], result=1

현재 추 w	result	설명
1	$1 \geq 1$ → result+=1→2	1을 추가, 측정 범위 [1, 1] 확장
1	$2 \geq 1$ → result+=1→3	1을 추가, 측정 범위 [1, 2] 확장
2	$3 \geq 2$ → result+=2→5	2를 추가, 측정 범위 [1, 4] 확장
3	$5 \geq 3$ → result+=3→8	3을 추가, 측정 범위 [1, 7] 확장
6	$8 \geq 6$ → result+=6→14	6을 추가, 측정 범위 [1, 13] 확장
7	$14 \geq 7$ → result+=7→21	7을 추가, 측정 범위 [1, 20] 확장
30	21<30: 종료	30은 현재 범위를 확장할 수 없음

결과: 측정할 수 없는 가장 작은 무게는 result=21입니다.

위 내용들을 기반으로 코드 설계를 해보도록 하겠습니다.

Step3. 코드 설계

1. 주어진 저울추를 오름 차순으로 정렬합니다.
2. result = 1 을 지정합니다.
3. 저울추를 순회하면서 현재 추가 result보다 크다면 순회를 멈춥니다. 그렇지 않다면 result += 현재 저울추를 진행합니다.
4. 최종적으로 result를 출력합니다.

Step4. 코드 구현

import sys
N = int(sys.stdin.readline().strip())
weight = list(map(int, sys.stdin.readline().split()))
def sol(weight):
    weight.sort()
    result = 1
    for w in weight:
        if result < w:
            break
        result += w
    return result
print(sol(weight=weight))

• 시간 복잡도:

  1. 정렬:

     • 주어진 저울추 배열을 오름차순으로 정렬하는 데 $O(N \log N)$의 시간이 소요됩니다.

  2. 순회 및 연산:
     - 정렬된 배열을 한 번 순회하며 가능한 무게를 누적하므로 $O(N)$의 시간이 소요됩니다.

     따라서, 전체 시간 복잡도는 $O(N \log N)$입니다.

• 결과:
  

---

4. 마무리

이번 문제는 그리디 알고리즘과 정렬을 활용해 해결했습니다. 저울추를 오름차순으로 정렬한 뒤, 현재 가능한 무게 범위를 순차적으로 확장하며, 확장할 수 없는 첫 번째 무게를 결과로 출력하는 방식입니다.

이 접근 방식은 현재 상태에서 가장 작은 추를 선택해 가능한 무게를 확장하는 최적의 선택을 반복하는 그리디 전략에 해당하며, 시간 복잡도는 $O(N \log N)$로 문제의 제약 조건을 충분히 만족합니다.

이번 문제를 통해 그리디 알고리즘의 효율성과 정렬의 중요성을 다시 한 번 확인할 수 있었으며, 주어진 조건을 정확히 이해하고 효율적인 알고리즘을 설계하는 과정이 중요하다는 점을 배웠습니다.

전체 코드는 다음 링크에서 확인할 수 있습니다.

읽어주셔서 감사합니다.