[C/C++] 백준 #2437 저울(탐욕 알고리즘)

이번 문제는 탐욕 알고리즘을 이용하여 풀면 됩니다.

 

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

2437번: 저울

 

balance

우리에게는 천칭저울로 알려진 무게를 재는 도구입니다.  한쪽에는 무게를 알고지 하는 물체를 다른 한쪽에는 추를 놓음으로써 평형을 이루는 지점을 찾아서 물체의 무게를 알 수 있습니다.

 

저울추가 N 종류 주어지면, 우리는 이 저울추 N개를 가지고 만들 수 있는 숫자들을 생각하면 됩니다.  어떻게 보면 코인 문제와 비슷한데, 코인 문제는 경우의 수를 따지지만, 여기서는 만들 수 없는 최소의 수를 알아내면 됩니다.

 

저는 탐욕 알고리즘을 생각했습니다.  모든 추를 크기순으로 정렬한 후,

첫번째에서 k번째 추를 가지고 1부터 s-1까지의 숫자를 만들 수 있다면, 

1) 만약 k+1번째 추 무게 $m_{k+1}$가 s보다 큰 값이라면 s 값을 만들 수 없게 됩니다.  왜냐하면 1~k까지 추로 만들 수 있는 무게는 s-1까지이기 때문입니다.  그래서 이 경우 답은 s가 됩니다.

2) 만약 k+1번째 추 무게가 s보단 작거나 같은 값이라면, 우리는 1~k+1까지의 추로 $m_{k+1}+s-1$까지의 무게를 만들 수 있습니다.

왜냐하면 1~s-1 무게는 1~k번째 추를 이용해서 만들 수 있고, $m_{k+1}$의 값이 s보다 작거나 같으므로, k+1번째 추를 무조건 이용하면, $m_{k+1}$부터  $m_{k+1}+s-1$ 까지의 무게를 잴 수 있으며, s 값은 반드시 저 범위안에 들어가게 됩니다. 

3) s를 $m_{k+1}+s$로 바꾸어서 다음번 추를 검사합니다.

 

제가 작성한 소스입니다.

//--------------------------------------
//    baekjoon #2437 - Scale
//        - by Aubrey Choi
//        - created at 2019-08-05
//--------------------------------------
#include <stdio.h>
#include <algorithm>

int main()
{
    int n, v[1000], min=1;
    scanf("%d", &n);
    for(int i=0;i<n;i++) scanf("%d", v+i);
    std::sort(v, v+n);
    for(int i=0;i<n;i++) { if(v[i]>min) break; min += v[i]; }
    printf("%d\n", min);
}