[백준 1744번] 수 묶기 (C++)

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

1744번: 수 묶기

---

수 묶기 문제에서 큰 값과 큰 값을 곱해주면, 합이 최대가 되도록 해줄 수 있습니다. 

 

하지만, 입력으로 0 이하의 숫자들도 주어질 수 있습니다. 

따라서 양수와 0 이하의 숫자를 구분할 필요가 있습니다. 

 

알고리즘의 기본 틀은 아래와 같습니다. 

1. 양수와 음수를 구분하여 각각의 배열에 저장한다. 
2. 양수 배열(p)과 음수 배열(m)을 정렬한다. 
3. 양수 배열
   1. p[i + 1]이 양수이면, p[i], p[i + 1]을 곱해준다.
   2. p[i + 1]이 1이면, p[i], p[i + 1]을 더해준다.
4. 음수 배열
   1. p[i]와 p[i + 1]을 곱해준다.

 

아래는 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;

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

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

    sort(p.begin(), p.end(), greater<>());    // 양수는 내림차순으로 정렬
    sort(m.begin(), m.end());    // 음수는 오름차순으로 정렬
    
    int ans = 0;
    if(p.size() % 2 != 0) ans += p[p.size() - 1];   // 양수가 홀수개인 경우 마지막 요소를 더해준다.
    for(int i = 0; i < (int) p.size() - 1;){
        if(p[i + 1] == 1) ans += p[i] + p[i + 1];
        else if(p[i + 1] > 0) ans += p[i] * p[i + 1];   // 양수인 경우
        i+=2;
    }

    if(m.size() % 2 != 0) ans += m[m.size() - 1];   // 0 이하의 숫자가 홀수개인 경우 마지막 요소를 더해준다.
    for(int i = 0; i < (int) m.size() - 1; i+=2)
        ans+= m[i] * m[i + 1];  

    cout << ans << "\n";    
}