백준 2437 저울 | C++

 

 

이번 포스팅은 백준 2437번 저울입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/2437

2437번: 저울

 

 

 

기본 알고리즘

그리디 알고리즘

 

셸 정렬 사용함

벡터와 sort 함수를 사용하면 코드의 길이와 실행 시간을 단축할 수 있다.

 

풀이

자연수 배열에서 배열 원소에 1이 존재하고, 배열의 (i-1)번째 원소까지의 누적합 sum에 대해

arr[i] <= sum + 1 을 만족하면 배열 원소의 부분합으로 1부터 sum까지의 자연수를 모두 표현할 수 있다.

 

 

 

전체 코드

 

//백준2437 저울                                                                
#include <iostream>
using namespace std;
 
void sortGapInsertion(int*, int, int, int);
void shellSort(int*, int);
 
int main() {
    int N; //list 원소 개수
    int list[1001]; //저울추 저장 배열
    int sum; //누적합 저장 변수
    int ans; //출력
    
    /*입력*/
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
 
    /*셸 정렬*/
    shellSort(list, N);
 
    /*풀이*/
    if (list[0] != 1) {
        ans = 1;
    }
    else {
        sum = list[0];
        for (int i = 1; i < N; i++) {
            if (sum + 1 < list[i]) {
                break;
            }
            sum += list[i];
        }
        ans = sum + 1;
    }
    
    /*출력*/
    cout << ans;
    return 0;
}
 
void sortGapInsertion(int* list, int first, int last, int gap) {
    int i, j, key;
    for (i = first + gap; i <= last; i++) {
        key = list[i];
        for (j = i - gap; j >= 0 && list[j] > key; j -= gap) {
            list[j + gap] = list[j];
        }
        list[j + gap] = key;
    }
}
 
void shellSort(int* list, int n) {
    int gap;
    for (gap = n / 2; gap > 0; gap /= 2) {
        if (gap % 2 == 0) gap++;
        for (int i = 0; i < gap; i++) {
            sortGapInsertion(list, i, n - 1, gap);
        }
    }
}