Beakjoon 1744 수 묶기

16 Jan 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/1744

나의 풀이

1. 수열을 음수 부분과 음수가 아닌 부분으로 나눈다.
2. 음수가 아닌 부분에서 0과 1은 곱하면 항상 작아지기 때문에 묶지 않는다.
3. 기본적으로 양수끼리 묶을 때 큰 숫자끼리 묶으면 커진다. -> 큰 순서대로 묶음
4. 음수끼리 묶을 때 작은 숫자끼리 묶으면 커진다. -> 작은 순서대로 묶음
5. 0은 음수가 홀수개일 때 마지막 음수를 0으로 만들어 줄 수 있다.
6. 음수와 양수를 묶으면 항상 작아지기 때문에 묶지 못한 나머지 값은 따로 더해준다.

풀이 코드 : 1744 수 묶기

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(int a, int b){
    return a > b;
}

int main(){
    int N, num;
    scanf("%d", &N);

    vector<int> plus;
    vector<int> minus;

    for(int i=0;i<N;i++){
        scanf("%d",&num);
        if(num < 0)
            minus.push_back(num);
        else
            plus.push_back(num);
    }

    sort(plus.begin(), plus.end());
    sort(minus.begin(), minus.end(), compare);

    int answer = 0;
    
    while(!plus.empty()){
        int size = plus.size();
        if(size < 2) break;
        else{
            if(plus[size-1] <= 1 || plus[size-2] <= 1) break;
            int first = plus.back();
            plus.pop_back();
            int second = plus.back();
            plus.pop_back();
            answer += first*second;
        }
    }

    while(!minus.empty()){
        int size = minus.size();
        if(size < 2) break;
        else{
            int first = minus.back();
            minus.pop_back();
            int second = minus.back();
            minus.pop_back();
            answer += first*second;
        }
    }

    while(!plus.empty()){
        int first = plus.back();
        plus.pop_back();
        if(first == 0 && !minus.empty()){
            minus.pop_back();
        }
        else{
            answer += first;
        }
    }
    if(!minus.empty()) answer += minus.back();

    printf("%d", answer);
}

채점결과