[백준(BOJ)] 1744번 : 수 묶기 - C++[CPP]

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

1744번: 수 묶기

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그리디 알고리즘
• 정렬

 

---

 

⊙ 문제 접근 과정

 

진짜 엄청 많이 틀리고 맞췄다...

단순히 정렬하고 높은 수끼리 곱하고 음수는 음수끼리 곱하면 될 줄 알았던 내 과오였다.

 

문제에 예외 케이스가 생각보다 다양하게 존재한다.

 

첫 번째로 누구나 생각할 수 있는 음수 X 음수 조합

        음수 X 음수 = 양수로 최댓값을 극대화할 수 있다.

 

두 번째로 0과 음수 조합

         0 X 음수 = 0으로 음수를 없앰으로써 최댓값을 극대화할 수 있다.

 

세 번째로 1 X 1 조합

         1 X 1 = 1이다. 하지만 1 + 1은 2이다.

         곱셈이 아닌 덧셈으로써 최댓값을 극대화할 수 있다.

 

마지막으로 1이 들어간 조합

        양수 X 1 = 양수이다. 하지만 양수 + 1은 양수 +1이다.

        마찬가지로 곱셈이 아닌 덧셈으로써 최댓값을 극대화할 수 있다.

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
vector<int> pLus;
vector<int> mInus;

int main() {
    cin >> N;

    for(int i=0;i<N;i++) {
        int x;
        cin >> x;
        if(x>0) 
            pLus.push_back(x);
        else
            mInus.push_back(x);
    }

    sort(pLus.rbegin(),pLus.rend());
    sort(mInus.begin(),mInus.end());

    int total=0;
    int ps = pLus.size()-1;
    int ms = mInus.size()-1;

    if(pLus.size()%2) {
        for(int i=0;i<ps;i+=2) {
            if(pLus[i] ==1 || pLus[i+1] ==1){
                total+=pLus[i]+pLus[i+1];
            } else total+=pLus[i]*pLus[i+1];
        }
        total+=pLus[ps];
    } else {
        for(int i=0;i<ps;i+=2) 
            if(pLus[i] ==1 || pLus[i+1] ==1){
                total+=pLus[i]+pLus[i+1];
            } else total+=pLus[i]*pLus[i+1];
    }

    if(mInus.size()%2) {
        for(int i=0;i<ms;i+=2)
            total+=mInus[i]*mInus[i+1];
        total+=mInus[ms];
    } else {
        for(int i=0;i<ms;i+=2)
            total+=mInus[i]*mInus[i+1];
    }

    cout << total;
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

누군가에게 도움이 되길 바라며...

 

좋아요는 로그인하지 않아도 누를 수 있습니다!