링크
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 이하이다.
출력
첫째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다.
풀이
처음에는 set, DP 등의 방법으로 풀어보려고 하였으나 시간초과로 인해 해결할 수 없었다. 결국 이 문제는 수학적으로 어떻게 접근하느냐가 관건이었다.
먼저 수를 배열에 넣고 오름차순으로 정렬시킨다.
그 다음 양의 정수 최솟값인 1(i)부터 만들어질수 있는지 차례로 검사한다.
동시에 배열 맨 앞부터 검사하면서 현재 i보다 같거나 작으면 i값에 배열의 값을 추가한다.
만약 i보다 크다면 반복문을 종료시킨다.
예를 들어 위 풀이를 검증해보겠다.
정렬된 추들의 배열 [1,1,2,3,6,7]을 살펴보자.
| 추가된 추의 무게 | 만들 수 있는 무게 |
|---|---|
| 1 | 1 |
| 1 | 1,2 |
| 2 | 1,2,3,4 |
| 3 | 1,2,3,4,5,6,7 |
| 6 | 1,2,3,4,5,6,7,8,9,10,11,12,13 |
| 7 | 1~20 |
여기서 무게가 30인 추가 추가된다면 무게 21을 만들어낼 수 없다.
무게가 22인 추가 추가되어도 마찬가지이다.
따라서 다음과 같은 규칙들이 발견된다.
1) 추가하는 추의 무게가 그 전 단계의 [만들 수 있는 무게의 최대값+1],(j)보다 크다면 j를 만들 수 없다.
2) 새로 추가된 추는 그 전 단계의 [만들 수 있는 무게의 최대값]+[추가된 추의 무게]까지의 무게를 만들어낼 수 있다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int N;
cin >> N;
int num;
vector<int> v;
for (int i = 0; i < N; i++) {
cin >> num;
v.push_back(num);
}
sort(v.begin(), v.end());
int result = 1;
for (int i = 0; i < v.size(); i++) {
if (v[i] > result)
break;
result += v[i];
}
cout << result;
return 0;
}
