[2437] 저울(C++)

🎅🏻 문제

2437번: 저울

 

 

🧣 해결 방법

예를 들어 추의 무게가 (3, 1, 6, 2, 7, 30, 1) 이렇게 주어졌다면

오름차순 정렬을 하고 처음부터 각 인덱스까지의 추의 무게를 합한 sum 은 아래의 표와 같다.

sum = 처음부터 각 인덱스까지의 추의 무게의 합

즉, sum에 저장된 값에 해당하는 무게까지는 우리가 만들 수 있다는 뜻이 된다.

ex) sum = 7이면 무게가 1인 것부터 7인 것까지 모두 만들 수 있다는 뜻

 

i가 4일때부터 한번 차근차근 봐보자.

1) i = 4, sum = 7

현재 내가 무게 7인것까지는 구현할 수 있는데 weight[4] = 6이므로 

무게가 6인 것은 당연히 구현 가능하다.

 

2) i = 5, sum = 13

현재 내가 무게 13인것까지는 구현할 수 있는데 weight[5] = 7이므로 

무게가 7인 것은 당연히 구현 가능하다.

 

3) i = 6, sum = 20

현재 내가 무게 20인것까지는 구현할 수 있는데 weight[6] = 30이므로

무게가 21인것부터 49까지는 만들 수 없다.

 

즉, weight[i] > (sum + 1)이라면 (sum + 1)의 무게는 만들 수 없다는 뜻이기 때문에 (sum + 1)을 답으로 출력하고 종료하면 된다.

 

이때 내가 계속 헷갈렸던 부분은, 

weight[i] > (sum + 1) 여기서 왜 등호가 붙으면 안되는지였다..

깨닫고 보니 되게 어이없는 고민이였는데,

 

예를 들어 weight[i] = 9이고 sum = 8이라면 

weight[i] == (sum + 1) 이 된다.

그런데 무게가 9인 추가 있기 때문에 (sum + 1) 인 9는 당연히 구현할 수 있는 것이고,

따라서 등호는 없어야 한다❗️

 

 

🎄 내 풀이

// [2437] 저울
// https://www.acmicpc.net/problem/2437
// 그리디 알고리즘

#include <cstdio> 
#include <vector> 
#include <algorithm> 
using namespace std; 

int main() 
{ 
	int n, tmp, sum = 1; 
	scanf("%d", &n);
	vector<int> weight; 
	for (int i = 0; i < n; i++) { 
		scanf("%d", &tmp);
		weight.push_back(tmp); 
	} 
	
	sort(weight.begin(), weight.end()); 

	if (weight[0] != 1) {
		printf("1\n");
	}
	else { 
		for (int i = 1; i < n; ++i) { 
			if (weight[i] > sum + 1) {
				break; 
			}
			sum += weight[i]; 
		} 
		
		printf("%d\n", sum + 1);
	} 
}