백준 2437번 저울

🔒[문제 url]

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

🔑알고리즘

무게추를 오름차순으로 정렬한다.

• 왜 오름차순으로 정렬하는가?
  • 현재 가지고 있는 추들ex) 1 1 2로 $1 \le k \le 4$ 에 해당하는 모든 수의 무게를 만들 수 있다고 가정하자. 그렇다면 무게가 $5$인 추를 추가한다면, $1 \le k \le 9 = (4 + 5)$ 에 해당하는 모든 수의 무게를 만들 수 있게된다.
    마찬가지로, 또다시 무게가 $6$인 추를 추가한다면 $1 \le k \le 15 = (9 + 6)$ 에
    해당하는 모든 수의 무게를 만들 수 있게된다.
    만약 여기서 무게가 $17$인 추를 추가한다면? $16$을 만들 수 없으므로 16이 답이 된다.
    따라서, 오름차순 정렬을 함으로써 만들 수 있는 무게를 Greedy하게 넓혀간다.

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
#include <algorithm>
using namespace std;

int n;
int weight[1001];

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> weight[i];
}


void SOLVE()
{
    sort(weight, weight + n);

    int maxMeasure = 1; // 만들 수 있는 무게인지 확인할 무게
    for (int i = 0; i < n; i++)
    {
        // 현재의 추를 추가해도 만들 수 없는 무게라면
        if (maxMeasure < weight[i])
            break;
		// 현재 추를 추가함으로써 maxMeasure-1까지의 무게를 만들 수 있게된다.
        else maxMeasure += weight[i];
    }
    cout << maxMeasure;
}



int main()
{
    INPUT();

    SOLVE();

}

🥇문제 후기

음.. 골드 상위부터는.. 코드 구현은 쉬우나 아이디어 떠올리기가 어려운 경우가 많군요!