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

문제 링크: https://www.acmicpc.net/problem/2437

2437번: 저울

 

문제풀이 자체는 정말 쉬운데, 생각하는 과정이 필요했던 문제입니다.

N은 1 이상 1,000 이하이다. 라는 문제 조건을 가진다.

즉 모든 추들을 더하고 빼며 모든경우의 수를 도출(dfs방식)하는 방식으로는 시간 초과를 받을 수밖에 없다.

우선은 누적합 개념에 대해서 이해하셔야 합니다. 

 

for (int i = 0; i <= n; i++) {
		if (arr[i] > sum + 1) {
			break;
		}
		sum += arr[i];

	}

정렬되어 있는 상태라면 위와 같은 방법으로 O(n) 만에 측정할 수 없는 결과값을 도출할 수 있습니다.

sum은 0부터 시작되며 정렬되어 있는 arr배열에서 가장 작은 값부터 하나씩 증가하며 값을 확인합니다. sum + 1 보다 클 경우 sum + 1에 해당하는 값은 측정할 수 없기 때문에 break를 써서 반복문에서 나가게 되는 구조입니다. 

 

 

 

 

 

아래는 정답코드 입니다. 

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

int n = 0, len = 1;
int arr[1001];
int sum = 0;


int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	sort(arr, arr + n); //오름차순 정렬

	for (int i = 0; i <= n; i++) {
		if (arr[i] > sum + 1) {
			break;
		}
		sum += arr[i];

	}

	cout << sum + 1 << endl;
}

위처럼 간단한 방식으로 정답을 도출할 수 있습니다.