백준 2437번 저울

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

문제를 잘 못 읽어서 두번 틀린 쉬운 그리디(greedy) 알고리즘 문제였습니다.

문제에서는 한 쪽에만 추를 올릴 수 있다고 했지만 저는 반대쪽에도 올릴 수 있다고 임의로 판단하였기 때문에 틀렸습니다.

알고리즘은 아래와 같습니다.

1. 주어진 숫자들을 배열에 넣고 오름차순 정렬을 합니다.

2. 다음에 등장하는 숫자가 (누적합 + 1) 이하라면 누적합 + 1까지의 숫자들은 기존의 숫자들의 조합으로 모두 표현 가능합니다. 

->초기에 1을 더했으므로 누적합 + 1

3. 하지만, 다음에 등장하는 숫자가 (누적합 + 2) 이상이라면 기존의 숫자들의 조합으로 (누적합 + 1) 표현이 불가능하므로 (누적합 + 1)을 출력해줍니다. 

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

const int MAX = 1000000000 + 1;

 

int N;

vector<int> v;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        cin >> N;

 

        v.resize(N);

        for (int i = 0; i < N; i++)

                 cin >> v[i];

        sort(v.begin(), v.end());

 

        //1이 없다면

        if (v[0] != 1)

                 cout << 1 << "\n";

        else

        {

                 int sum = 1; //v[0]

                 //현재까지의 합 + 1 보다 큰 값이 다음 인덱스에 저장된 수라면

                 //이전의 추들로 무게를 구할 수 없다

                 for (int i = 1; i < N; i++)

                 {

                         if (v[i] > sum + 1)

                                 break;

                         sum += v[i];

                 }

                 cout << sum + 1 << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~