[ 백준 / 2437 ] 저울 (C++)

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

 

난이도 : 골드 2 
알고리즘 유형 : 정렬, 그리디 
풀이 시간 : 49분 

문제 풀이 

주어진 무게추를 사용하여 만들 수 없는 무게 중 가장 작은 값을 출력하는 문제이다.

본 문제를 처음 마주할 때 생각할 수 있는 알고리즘은 그리디, DP 가 있다. 하지만 주어진 범위를 잘 살펴보면 $N ≤ 1000, 각 무게추의 무게 ≤ 1000000$이기 때문에 입력으로 $1000000$의 무게가 $1000$개 들어오는 경우 1차원 DP 배열에 저장할 수 없다. 따라서 우리는 무게를 낮은 순으로 오름차순 정렬한 뒤, 만들수 없는 최소 무게가 나올 때 반복문을 빠져나오는 그리디 알고리즘을 사용할 수 있다.

 

먼저 무게추 배열을 입력받고, 오름차순으로 정렬해주자. 

이후, 첫번째 무게추의 무게를 먼저 확인하여 현재 만들 수 있는 최대 무게(`cur_num`)로 지정해주어야 하는데 이 때, 현재 무게가 1보다 크게 되는 경우에는 1 무게를 만들 수 없기 때문에 바로 1을 출력하고 종료해주어야 한다.

이후 만들 수 없는 경우에 대해서 판단해주어야 하는데, 두 가지 경우를 만족해야 한다.

 

1. 현재 만들 수 있는 최대 무게 (`cur_num`) 가 현재 무게추의 무게(`scales[i]`)보다 작거나 같은 경우

2. 현재 만들 수 있는 최대 무게 + 1 (`cur_num + 1`) 을 한 값보다 현재 무게추 무게 (`scales[i]`) 가 더 큰 경우

 

이 두 가지 경우를 충족시킨다면, 현재 만들 수 있는 최대 무게(`cur_num`)가 최대가 되므로 종료한다.

아닌 경우에는, 현재 무게추의 무게(`scales[i]`)만큼 만들 수 있는 최대 무게 (`cur_num`)를 1씩 증가시켜주면 된다.

 

시간복잡도를 계산해본다면, 최악의 경우 $O(n^2)$가 된다.

 

코드

/*
측정할 수 없는 양의 정수 무게 중 최솟값을 구하자

풀이:
그리디, 정렬 
나올 수 있는 숫자를 더해가면서 비교하기
만약 맨 앞 숫자와 현재 숫자를 더한 값이 현재 값보다 크다면, 종료
1000 x 1000 
*/

#include <iostream>
#include <algorithm>
#include <vector>
#define INIT cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;

int n;
vector<int> scales;

int main() {
	cin >> n;
	int tmp;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		scales.push_back(tmp);
	}

	// 0. 오름차순 정렬
	sort(scales.begin(), scales.end());

	// 1. 첫 녀석은 그냥 넣어주기
	int cur_num = scales[0];
    // 예외 처리 : 무게추 1이 없을 경우
	if (cur_num > 1)
		cout << 1 << '\n';
	else {
		// 2. 순회 시작
		for (int i = 1; i < n; i++) {
			// 더 큰 경우에 대해서 판단
			if (cur_num <= scales[i]) {
				if (cur_num + 1 < scales[i])
					break;
			}
			for (int j = 0; j < scales[i]; j++)
				++cur_num;
		}

		cout << cur_num + 1 << '\n';
	}

	return 0;
}

배운 점 

시간복잡도도 중요하지만, 공간복잡도 역시 중요하다는 것을 느꼈다. 그리디로 풀었을 경우, set을 사용해서 증가된 값을 저장해주었는데, 메모리초과가 떴고, 의미없이 값을 저장하고 있다는 것을 파악했다. 이렇게 코드를 작성할 때 메모리에 대해서 지속적으로 신경써가며 문제를 풀어야겠다.