99클럽 코테 스터디 9일차 TIL + 저울(백준 2437번)

✅ 오늘의 학습 키워드

• 그리디 알고리즘
• 정렬 (오름차순)
• 연속된 추들로 측정할 수 없는 양의 정수 무게 중 최솟값 구하는 방법

---

✅ 공부한 내용

- 문제 요약

(백준 문제 링크: https://www.acmicpc.net/problem/2437)

• N개의 저울 추가 주어졌을 때, 이 추들로 측정할 수 없는 가장 작은 양의 정수 무게를 구하는 문제다.
• 한쪽은 물체, 다른 한쪽은 추를 놓을 수 있다. 즉, 연속적인 N개의 추들로 물체의 무게를 표현하는 저울이다.
• ex) 저울추 3, 1, 6, 2, 7, 30, 1인 경우 측정할 수 없는 가장 작은 양의 정수 무게는 21이다.

- 풀이 로직

1. 추들을 오름차순으로 정렬한다. (작은 것부터 고려)
2. sum 변수를 사용해서 현재까지 추들로 만들 수 있는 연속된 무게의 최댓값 변수 저장.
3. 각 추를 순서대로 확인하면서:
   • 현재 추의 무게가 sum+1 보다 크다면, sum+1은 만들 수 없는 최소 무게다.
   • 그렇지 않다면, 이 추를 사용하여 범위를 sum + weights[i] 까지 확장할 수 있다.
4. 모든 추를 다 사용했다면, 측정할 수 없는 가장 작은 양의 정수 무게 sum+1 출력.

---

✅ 오늘의 회고

- 😳 어떤 문제가 있었고, 나는 어떤 시도를 했는지

측정할 수 없는 최소 무게를 어떻게 설정해줘야 하는지가 어려웠다. 하지만 찾아보니 정말 간단...허헣..."sum + 1"이 왜 측정할 수 없는 최소 무게가 되는지 직접 손 코딩을 통해 예제를 넣어서 원리를 파악하려고 이해해 보았다.

- 🤔 어떻게 해결했는지

귀납적 사고로 생각해 보자. 현재 1 ~ sum까지 모든 무게를 만들 수 있다면 다음으로 필요한 무게는 당연히 sum+1이다.
만약 새 저울추가 sum+1보다 크다면 이 무게는 만들 수 없게 된다. 즉, 연속된 무게가 깨지는 지점이 바로 측정할 수 없는 최소 무게이다.

 

이해를 돕기 위해 아래의 저울추를 통해 측정할 수 없는 최소 무게를 알아내는 알고리즘을 통해 생각해 보자.

    sort(weights.begin(), weights.end()); // 추들을 오름차순 정렬 (작은 것부터 고려)
    
    int sum = 0; // 현재까지 추들로 1부터 sum까지 모든 무게를 만들 수 있는 무게의 최대값

    for(int i = 0; i < N; i++){
        // 현재 추가 sum + 1보다 크면, sum+1은 만들 수 없는 최소 무게
        if(weights[i] > sum + 1) {  
            break;
        }
        sum += weights[i]; // 현재 추를 사용하여 만들 수 있는 무게의 범위 추가
    }

 

예제를 통해 위의 알고리즘 동작 과정을 파악해 보자.

예를 들어, 추들 [1, 2, 5]가 있다고 가정하자.

 

1. 초기 상태: sum = 0 (아직 아무 무게도 측정 불가)

2. 첫 번째 추(1) 사용:

• 1 ≤ sum+1(=1)이므로 연속성 유지 가능
• sum = 0+1 = 1 (1까지 측정 가능)

3. 두 번째 추(2) 사용:

• 2 ≤ sum+1(=2)이므로 연속성 유지 가능
• sum = 1+2 = 3 (1, 2, 3까지 측정 가능)

4. 세 번째 추(5) 확인:

• 5 > sum+1(=4)이므로 연속성 깨짐!
• 알고리즘 종료, 4가 측정할 수 없는 최소 무게

이 추들로 1, 2, 3, 5, 6, 7, 8을 측정할 수 있지만, 4는 측정할 수 없다.

이외에 여러 가지 예제들을 넣어보았을 때, 왜 sum + 1이 되는지 알 수 있었다.

- 🤩 무엇을 새롭게 알았는지

골드라고 겁먹었는데 생각보다 간단한 것을 보고 아쉬웠다. 그리디 알고리즘처럼 정렬을 기반으로 최적의 값을 반복하면서 최소 무게를 찾아내는weights[i] > sum + 1조건은 단순해 보이지만, 이를 도출하는 과정은 깊은 수학적 사고가 필요했다. 이 조건문을 떠올리는 게 어렵지 않았을까 라는 생각이 든다. 정렬된 데이터에서 특정 조건을 만족하는 최솟값을 찾는 효율적인 접근법을 익혔다.

---

✅ 전체 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {

    int N;
    cin >> N; // 저울추의 개수

    vector<int> weights(N);
    for(int i = 0; i < N; i++){
        cin >> weights[i];
    }

    sort(weights.begin(), weights.end()); // 추들을 오름차순 정렬 (작은 것부터 고려)

    int sum = 0; // 현재까지 추들로 1부터 sum까지 모든 무게를 만들 수 있는 무게의 최대값

    for(int i = 0; i < N; i++){
        // 현재 추 weights[i]가 sum + 1보다 크면, sum+1은 만들 수 없는 최소 무게
        if(weights[i] > sum + 1) {  
            break;
        }
        sum += weights[i]; // 현재 추를 사용하여 만들 수 있는 무게의 범위 추가
    }

    cout << sum + 1 << '\n';

    return 0;
}