[백준] No.2437 - 저울 (C++)

문제

 

www.acmicpc.net/problem/2437

2437번: 저울

 

풀이

 

solved.ac 난이도: Gold3

 

그리디 알고리즘 문제이지만 DP문제에서 많이 본 유형이라 문제 분류를 몰랐다면 DP로 접근했을 듯한 문제였다.

 

해당 문제의 그리디 알고리즘은 다음과 같다.

 

일단 추를 무게의 오름차순으로 정렬했다 가정하자.

지금까지 idx번째의 추까지 사용하여 만들 수 있는 무게들 중 가장 큰 것을 end_num라고 하자.

다음 추 idx+1를 추가적 이용하여 만들 수 있는 무게들은 0,1,2 ~ end_num들에 모두 idx+1의 무게를 더한 것과 같다.

즉, end_num은 end_num +weight_list[idx+1]이 되고 만들 수 있는 무게는 1~end_num+weight_list[idx+1]이다.

 

만약 다음 추의 무게(weight)가 end_num+1 보다 크다면

0,1,2 ~ end_num들에 모두 해당 값을 더해주어도만들 수 있는 무게는 0~end_num에서 끊기고, weight~end_num+weight가 된다.

따라서 이런 경우 정답은 만들 수 있는 최댓값의 다음 값인 end_num+1이다.

 

예를 들어 

1 1 2 2 8의 추가 주어진다면 

 

1 -> end_num: 1

1 -> end_num: 2

2 -> end_num: 4

2 -> end_num: 6

8 -> end_num +1 < 8

 

따라서 답은 end_num+1인 7이다.

 

추가적으로 end_num +1 < weight_list[idx]인 경우가 없을 수도 있기 때문에

이 경우에는 최종 end_num에 +1 한 만들 수 없는 무게의 최솟값이 답이 된다.

 

코드

 

	#include <iostream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	int weight_num;
	int weight_list[1000];
	int main() {
	ios_base::sync_with_stdio(0);
	cin>>weight_num;
	for(int i=0; i<weight_num ; ++i)
	cin>>weight_list[i];
	sort(weight_list, weight_list+weight_num);
	int end_num =0;
	int min_num = -1;
	for(int idx=0; idx<weight_num ;++idx){
	if(end_num +1 >= weight_list[idx])
	end_num += weight_list[idx];
	else{
	min_num = end_num+1;
	break;
	}
	}
	if(min_num == -1) //for문이 break되지 않은 경우
	min_num = end_num +1;
	cout<<min_num<<'\n';
	return 0;
	}

view raw [BaekJoon]_2437_저울.cpp hosted with ❤ by GitHub