[백준/C++] #1744 수묶기 (Greedy)

문제

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

 

풀이 (37m / 한번에 x)

 

수들끼리 짝지어서 곱해 더할 수도 있고, 그냥 더할 수도 있는데, 합이 최대가 되도록 해야했다. 

생각났던 로직 순서대로

- 가장 큰 양수부터 시작해서 두개씩 짝지어서 곱해서 더함
- 양수의 개수가 홀수라면 남은 양수는 그냥 더함

- 1은 다른 양수랑 곱해서 더하기보다 그냥 더하는게 더 커지니 따로 그냥 더함

- 0도 있고 홀수도 있다면, 0 개수만큼 가장 작은 홀수들 부터 없애기

+) 음수가 2개 이상이라면 0이랑 상쇄시키기보다 일단 가장 작은 홀수들부터 두개씩 곱해서 양수 만들기

+) 음수가 홀수개이고, 0이 있다면 마지막으로 가장 큰 음수는 0이랑 상쇄시키기. 0이 없다면 그냥 더하기

 

생각보다 예외 케이스들이 바로바로 생각나지 않았던 문제였다. (마지막 + 부분은 생각이 너무 늦게남..)

앞으로는 코드 짜기 전에 예외 케이스를 좀 더 생각해보자!!

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/*
수 묶기
- 양수는 큰 수끼리 곱
- 1은 그냥 더함
- 음수는 작은 수끼리 곱
- 음수 1개 남았고 0이 있으면 곱해서 무시
*/

int n; 
int res = 0;
vector<int> v;

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        int nn; cin >> nn; 
        v.push_back(nn);
    }
    
    sort(v.begin(), v.end(), greater<int>()); // 내림차순
    
    int idx = 0;

    // 양수 중 1보다 큰 애들끼리 곱
    while(idx + 1 < v.size() && v[idx] > 1 && v[idx + 1] > 1){
        res += v[idx] * v[idx + 1];
        idx += 2;
    }

    // 1 이상 양수는 더함
    while(idx < v.size() && v[idx] >= 1){
        res += v[idx];
        idx++;
    }

    // 나머지 숫자들 (0 이하)
    vector<int> sub(v.begin() + idx, v.end());

    vector<int> negatives;
    bool hasZero = false;

    for (int num : sub) {
        if (num == 0) hasZero = true;
        else if (num < 0) negatives.push_back(num);
    }

    sort(negatives.begin(), negatives.end()); // 작은 음수부터

    int i = 0;
    // 가장 작은 음수끼리 곱함
    while (i + 1 < negatives.size()) {
        res += negatives[i] * negatives[i + 1];
        i += 2;
    }

    // 음수 1개 남았을 경우
    if (i == negatives.size() - 1) {
        if (!hasZero) {
            res += negatives[i]; // 0 없으면 그냥 더함
        }
        // 0 있으면 곱해서 무시 (아무 것도 안 더함)
    }

    cout << res;
}