[코딩테스트C++] 저울

오늘의 문제

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

저울

접근 방법

• 먼저 오름차순으로 정렬한다.
• 일단 1로 시작해야하고 그렇지않으면 1을 반환한다.
• 앞에서부터 더한다. 여기서 중요한점은 다음 더해야할 숫자가 지금까지 더해놓은 수+1보다 작거나 같아야한다.
• 왜? 이미 왼쪽은 1부터 총 합까지의 모든 수를 만들 수 있다. 따라서 새로운 숫자를 더하고나서 1부터 뺄 수 있다는 것
• 만약 더해놓은 수+1보다 크다면, 가장 작은 1을 빼도, 다음수를 만들 수 없다.

나의 풀이

#include <iostream>
#include <algorithm>
using namespace std;
int n;
const int MAX = 1000;
int weight[MAX];

// 저울
long long solution(){
    sort(weight, weight+n);
    if(weight[0] != 1)
        return 1;
    long long sum = 1;
    for(int i=1;i<n;i++){
        if(weight[i] > sum + 1)
            break;
        sum += weight[i];
    }
    
    return sum+1;
}

다른 풀이

#include <stdio.h>

void selectionSort(int array[], int inputNum) {
	for (int i = 0; i < inputNum; i++) {
		for (int j = i + 1; j < inputNum; j++) {
			int tmp;
			if (array[i] > array[j]) {
				tmp = array[i];
				array[i] = array[j];
				array[j] = tmp;
			}
		}
	}
}
int main(int argc, char* argv[]) {
	int inputNum;
	scanf("%d", &inputNum);

	int weights[1000];
	for (int i = 0; i < inputNum; i++)
		scanf("%d", &weights[i]);
	selectionSort(weights, inputNum);


	int last = 0;
	for (int i = 0; i < inputNum; i++) {
		if (weights[i] > last + 1) {
			break;
		}
		last += weights[i];
	}
	printf("%d", last + 1);
	return 0;
}

배울 점

• 정확히 나의 풀이와 같다.
• 다른점은 sort를 selection sort를 사용한것. selection sort는 내가 사용한 sort(quick sort)보다 같거나 느릴 수 있다. n^2이므로. quick sort는 최악이 n^2 평균이 nlogn