koitp SDS_TEST_BIGINT 큰수만들기

문제 링크입니다: https://koitp.org/problem/SDS_TEST_BIGINT/read/

그리디(greedy) 알고리즘 문제였습니다.

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

1. 첫 번째 숫자는 고정이지만 두 번째 숫자부터는 원하는대로 배치가 가능하기 때문에 오름차순 정렬을 해줍니다.

2. 작은 숫자부터 뺄셈을 해주면 가장 큰 수가 나오기 때문에 오름차순 정렬한 숫자들을 M만큼 뺄셈을 진행해주고 나머지는 더해주면 됩니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

int N, P, M;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int test_case;

        cin >> test_case;

 

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

        {

                 cin >> N >> P >> M;

                

                 vector<int> v(N);

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

                         cin >> v[j];

 

                 //greedy하게 접근하여 두 번째 숫자부터 오름차순 정렬

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

                 //처음 숫자는 고정

                 long long sum = v[0];

                 //오름차순 정렬한 상태에서 뺄셈을 M만큼 진행 후 나머지 덧셈

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

                 {

                         if (M)

                         {

                                 sum -= v[j];

                                 M--;

                         }

                         else

                                 sum += v[j];

                 }

 

                 cout << "#" << i << " " << sum << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

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