[백준/Baekjoon] 1744 수 묶기 C++ :: Greedy

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

1744번: 수 묶기

---

1. Logic

1. 1은 어떻게 계산 하던지 자기 혼자 더하는게 무조건 이득

2. 양수는 무조건 큰숫자부터 곱해서 더하고 혼자남으면 그냥 혼자 더히기

3. 음수는 절댓값이 큰 숫자부터 곱해서 더하고 혼자 남으면 그냥 더하기 or 0이 있으면 넘어가기

4. 0은 -1이 없거나 음수의 갯수가 짝수면 필요없지만 -가 홀수면 음수를 없애는데 사용

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n;
int zeroCnt = 0;

vector<int> positiveNum;
vector<int> negativeNum;

int main() {
    int ans = 0;

    cin >> n;

    for(int i = 0; i < n; i++) {
        int a; 
        cin >> a;

        if(a > 1)
            positiveNum.push_back(a);
        else if(a == 1)
            ans += 1;
        else if(a == 0)
            zeroCnt++;
        else if(a < 0) 
            negativeNum.push_back(a);
    }

    sort(positiveNum.begin(), positiveNum.end(), greater<>());
    sort(negativeNum.begin(), negativeNum.end());

    for(int i = 0; i < positiveNum.size(); i++) {
        if(positiveNum.size() - i == 1) {
            ans += positiveNum[i];
            continue;
        }
        ans += positiveNum[i] * positiveNum[i + 1];
        i++;
    }
    for(int i = 0; i < negativeNum.size(); i++) {
        if(negativeNum.size() - i == 1) {
            if(zeroCnt > 0) {
                zeroCnt--;
                continue;
            }
            ans += negativeNum[i];
            continue;
        }
        ans += negativeNum[i] * negativeNum[i + 1];
        i++;
    }

    cout << ans;
}

 

 

---

3. Feedback

 - 처음에는 수를 저장하는 컨테이너를 한곳에 다 몰아넣어서 풀으려고 했지만 이 문제에서는 0이 나올지도 모르고 양수의 종료점이 어디로 나오는지 정확히 안나오기 때문에 배열을 나누어서 풀었더니 쉽게 풀렸다. 

 

입력받는 배열을 나눠서 생각하는 것도  좋은 방법이다.

728x90