백준 BOJ 2437 - 저울

입시를 대충 끝내고 PS재활을 시작하면서 접한 첫 문제.

거의 1년동안 문제를 안풀엇기때문에 바로 답이 안떠올라서 태그부터 까보았다.

태그는 그리디 / 정렬

정렬시켜놓고 숫자를 출력시킨 다음에 생각을 시작했는데

마지막 값으로 들어온 30이 이질적이게 큰 것을 보면서

다른 모든 숫자의 합으로 30이 만들어질수 없다는 생각을 했다.

 

다른 모든 숫자의 합 을 부분합으로 구해준 다음에

부분합으로 앞선 숫자들을 전부 사용해도 만들수 없는 수가 입력으로 있는 경우

부분합+1 이 답이 된다.

입력에 1이 없는 경우 숫자 1부터 만들수 없어 1을 출력해야하니 이부분에 대해서

처리가 필요할듯.

 

AC받았다.

 

#include <bits/stdc++.h>
using namespace std;

int arr[1234] = {0};
int prefix[1234] = {0};

int main(){
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	cin >> n;
	
	for(int i=0; i<n; i++){
		cin >> arr[i];
	}
	
	sort(arr, arr+n);
	
	for(int i=0; i<n; i++){
		if(i) prefix[i] = prefix[i-1] + arr[i];
		else prefix[i] = arr[i];
	}
	
	if(prefix[0] != 1){ cout << 1; return 0; }
	
	for(int i=1; i<n; i++){
		if(prefix[i-1]+1 < arr[i]){
			cout << prefix[i-1]+1;
			return 0;
		}
	}
	cout << prefix[n-1]+1;
	return 0;
}

//앞의 k개를 더해서 prefix[k] 선언.
//prefix[k]+1 < arr[k+1] 인 경우 prefix[k]+1은 만들어낼수 없는 숫자가 됨 ㅁㄴㅇㄹ
//만일 모든 가정이 충족된다?
//prefix[last_k]+1