[G2] 백준 2437번 저울 C++ 그리디 알고리즘

리뷰

 

https://www.acmicpc.net/problem/2437

복잡하게 생각할 수록 더 나락에 빠지는 문제

 

 

전역 변수

• n : 주어지는 추의 개수를 저장할 변수
• lst : 추의 무게를 저장하기 위한 정수형 배열

 

함수

없음

 

 

문제풀이

1. n을 입력 받고, n개의 추의 무게를 입력 받아 lst배열에 저장해 준다.
2. sort메서드를 통해 lst배열을 오름차순으로 정렬해 준다.
3. 정수형 변수 ans를 1로 초기화 해준다.
4. n개의 추를 순회하며 현재 추가 ans보다 작거나 같은 경우 ans에 추의 무게만큼 더해준다.
5. ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

1. multiset을 사용하여 매 숫자마다 upper_bound 메서드를 통해 사용할 수 있는 추 중 가장 무거운 추를 추가해 줬다.
2. 예제의 정답은 나왔으나 결국 시간 초과를 받게 되었다.
3. 다른 문제를 풀다가 문득 그리디한 생각이 들어 정렬을 통한 풀이를 제출하였더니 AC를 받게 되었다.

 

참고 사항

1. 1 ~ 100번 요소를 갖고 300이라는 수를 만들 수 있다고 가정하자
2. 101번째 요소가 300이라면 1 ~ 101번 요소를 갖고 600이라는 수를 만들 수 있게 된다.
3. 이를 활용하면 문제 접근이 쉽다. (단, 정렬은 필수적으로 진행해 주어야 한다.)

 

정답 코드

#include<iostream>
#include<algorithm>
using namespace std;

int n;
int lst[1000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; ++i) cin >> lst[i];
	sort(lst, lst + n);

	int ans = 1;
	for (int i = 0; i < n; ++i) {
		if (lst[i] <= ans) ans += lst[i];
	}
	cout << ans;
}