백준 1744 - 수 묶기

1. 문제 정리
  - N개의 수열이 주어진다.

  - 수열의 순서는 바꿀 수 있으며 수열의 각 값은 서로 다른 수와 순서쌍으로 묶을 수 있다.(여기서 말하는 서로 다른 수는 인덱스가 다른 수로, 값은 같을 수 있다. 즉 자기 자신이 안 된다.)
  - 순서쌍으로 묶은 수는 서로 곱하여 하나의 수로 인식한다.

  - 모든 값의 합이 가장 크도록 한다.

 
2. 접근
  - 그리디 알고리즘으로 해결해야겠다고 생각하였다.

  - 가장 큰 수 두개의 곱이 가장 클 것이므로 내림차순으로 정렬한 뒤 문제를 풀고자 하였다.

  - 음수 간의 경우 가장 작은 수 두개의 곱이 가장 클 것이므로 음수의 경우는 오름차순으로 정렬해야 했다.

  - 양수가 내림차순, 음수가 오름차순인 이유는 벡터의 뒤에서부터 계산해나가기 위함이다.

  - 0은 어디에 들어가도 상관 없다.(이후 문제 풀이에서 설명하겠다.)
 
3. 풀이

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

int n;
vector<int> p;
vector<int> m;
vector<int> remain;

bool comp(int x, int y){
    if(x > y) return true;
    return false;
}

int max(int a, int b){
    if(a > b) return a;
    else return b;
}

long long greedy(vector<int> a){
    long long sum = 0;
    while(a.size() > 1){
        int i = a.size()-1;
        if(a[i]+a[i-1] >= a[i]*a[i-1]){
            sum += a[i];
        }
        else{
            sum += a[i]*a[i-1];
            a.pop_back();
        }
        a.pop_back();
    }
    if(a.size() == 1) remain.push_back(a[0]);
    return sum;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    cin >> n;

    for(int i = 0; i < n; i++){
        int input;
        cin >> input;
        if(input > 0) p.push_back(input);
        else m.push_back(input);
    }

    sort(m.begin(), m.end(), comp);
    sort(p.begin(), p.end());
    long long ans = greedy(p) + greedy(m);
    if(remain.size() == 2) ans += max(remain[0]+remain[1], remain[0]*remain[1]);
    if(remain.size() == 1) ans += remain[0];
    cout << ans;

}

  - vector<int> p : 양수를 저장할 벡터이다

  - vector<int> m : 음수를 저장할 벡터이다.

  - vector<int> remain : 수열 간의 곱과 합이 끝난 후 남는 마지막 수를 저장할 벡터이다.

  - bool comp(int a, int b) : 오름차순으로 정렬하기 위한 함수이다.

  - int greedy(vector<int> a) : a 벡터를 파라미터로 받아, a 벡터가 정렬된 순서로 조건에 따라 수열값을 sum에 더해나가 sum를 반환한다.

  여기서 조건은 벡터의 마지막 값과 그 앞의 값의 합과 곱 중 큰 것을 골라 합이 클 경우 sum에 합을 넣고, 곱이 클 경우 sum에 곱을 넣은 뒤 pop_back()을 이용해 넣은 값을 벡터에서 빼준다. while loop 마지막에 pop_back()을 한번 더 해줌으로 합의 경우는 결과적으로 1회, 곱의 경우는 결과적으로 2회 pop을 하여 값을 제거한다. 곱의 경우 2회인 이유는 두개의 곱이 sum에 저장되기 때문이다.

  그 후 순회하고 있는 벡터의 크기가 1 이하가 될 경우 while loop를 탈출하며, 벡터의 크기가 1일 경우는 remain 벡터에 그 값을 추가해준다.(이는 계산해야 할 값이 남아있음을 의미한다.)

 remain에 넣을 값을 바로 sum에 계산하지 않은 것은 해당 함수가 1회만 동작하는 것이 아닌 다른 greedy와 연계하여야 하므로, 다른 greedy에서 또한 remain 값이 남을 경우 케이스에 따라 계산하기 위함이다.

  - int main() : greedy 함수를 각 m, p 벡터를 파라미터로 작동하고, 그 값을 ans 값에 더해놓는다. 그 후 remain의 크기에 따라 remain의 크기가 2일 경우(m, p 벡터 각각에 한개의 잔여값이 있을 경우) 그 두 값을 다시 합과 곱에 대한 비교를 하여 ans 값에 더해준다.

  remain의 크기가 1일 경우 ans에 그 값을 더해주고 출력한다.

 
4. 소감

  이 문제는 좀 까다로웠다. 처음에는 그저 하나의 벡터에 모든 값을 넣고 내림차순으로 정렬한 뒤 문제를 풀었는데, 이 경우 음수 간의 곱에 대한 경우를 생각하지 못해 정답이 나오지 않았다. 그 후 음수와 양수를 따로 저장한 뒤 문제를 접근하였는데, 그제서야 풀었다.

  사실 그렇게 까다로운 문제는 아니었지만(이전 문제들 보다 한단계 더 생각하게 만든 정도였으니) 아직 내 실력이 모자란 감도 있어 헤맸던 것 같다. 앞으로는 더 어려운 문제도 풀 수 있도록, 더 다양한 문제를 풀 수 있도록 더 연습해야겠다.