저울

알고리즘 구분 : 그리디

문제

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

무게가 양의 정수인 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

문제 풀이

일단 입력받은 값들이 정렬되어 있지 않은 형태이기에, 정렬을 해야 한다.

처음에 푸는 과정에서 조합으로 모든 경우의 수를 구하면서, 빈 값을 찾는 방식으로 구현하고자 하였으나, N의 최대 범위가 1,000이고 모든 경우의 수를 구하여 계산할 경우, 무조건 시간 초과가 발생할 것이므로, 해당 방법은 사용할 수 없다고 판단하였다.

두 번째로는, 빈 값을 찾기 위해 1부터 일일이 증가시켜 가며, 만들 수 있는 가를 확인해 보는 과정으로 구현하려고 하였으나, 이 역시 각 값을 만들 수 있다는 것을 확인하는 함수가 반복적으로 사용되면 시간 초과가 날 수 밖에 없다고 판단하였다.

질문 게시판의 도움을 일부 받아, 문제에 다시 접근하였는데,
현재 뽑은 숫자가 지금까지 더한 숫자 보다 작다면, 그 수는 지금까지의 더한 수(result)부터 뽑은 수를 더한 값(result + v[i])까지 만들 수 있고, 크다면 지금까지 더한 숫자 +1이 만들 수 없는 최소의 수가 된다는 것이였다.

이를 풀어보자면, 기본적으로 result >= v[i] - 1이며, result이하의 수는 모두 만들 수 있는 상황에서, result + v[i]라는 수를 만든 상황으로 놓는다. 그렇다면, v[i] + 0, v[i] + 1, ···, v[i] + result까지의 수는 모두 만들 수 있다는 의미이다. 즉, result부터 result + v[i]사이의 모든 수를 만들 수 있다는 것이다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> v;
void solve();

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	while(n--) {
		int input;
		cin >> input;
		v.push_back(input);
	}
	
	solve();
	
	return 0;
}

void solve() {
	sort(v.begin(), v.end(), less<int>());
	
	int result = 1;
	for(int i = 0; i < v.size(); i++) {
		if(result < v[i]) {
			break;
		}
		
		result += v[i];
	}
	
	cout << result << endl;
}

• 문제 출처 : https://www.acmicpc.net/problem/2437
• 해당 풀이는 백준에서 "맞았습니다!!"판정을 받았습니다.