[백준OJ] 1744번 수 묶기

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

1744번: 수 묶기

---

 

-풀이-

먼저 수를 묶을때, 조건들이 필요하다.

1) 두 수를 곱했을때 양수가 되는가?

2) 두 수중 1이 포함됐나?

3) 수열중에 0이 포함되었나?

등등을 고려해야한다.

 

이 조건들을 고려하기위해서, 양수와 음수를 따로따로 분리를 시켜서, 1번 조건을 해결하려한다. 왜냐면 양수따로 음수따로 계산을 했을때, 양수*음수를 하는 경우를 방지할 수 있기때문이다.

 

수를 묶은다음 최댓값을 만들어야 하기때문에, 양수에서는 큰수*큰수, 음수에서는 작은수*작은수를 해주어야지 최댓값이 나오므로, 양수를 내림차순으로, 음수를 오름차순으로 정렬을 한다.

 

그런뒤, i번째와 i+1번째를 묶어서 곱하면 큰수*그다음 큰수 , 음수에선 작은수*그다음 작은수가 되기때문에 계산을 하기 편해진다.

하지만 양수에서 두 수중 1이 포함이 되었을때는 말이 달라진다. 예를들어 2와 1을 묶는다고 쳤을때 2*1로 2가 되는데, 따로따로 더해주면 3이 되기때문에, 두 수중 1이 포함이 된 상태라면, 각각 더해주는것이 더 큰수를 만들 수 있다.

 

양수와 음수 각각 했을때, 홀수개수인 부분에선 2개씩 묶고 남는숫자가 하나 나올것이다.

이때, 만약 수열에 0이 포함이 되어있다면, 양수와 묶는것이 최대일지, 음수와 묶는것이 최대일지, 아니면 각각 따로따로 더해주는게 최대일지 알아보자.

 

양수에서 2가 남았고, 0이있고, 음수에서 -1이 남았다고 해보자.

1) 양수*음수+0 = -2+0 = -2가된다.

2) 양수*0+음수 = 2*0-1=-1이된다.

3)양수+0+음수 = 2+0-1 = 1이된다.

4) 양수+0*음수 = 2+(0*-1) = 2가 된다.

 

당연한결과이다. 0이있다면, 음수를 지워주었을때 합이 최대가 되므로, 0이있다면 음수에 남은것과 묶어주면되고, 음수에 남은것이없다면 그냥 묶지않고 더해주면된다.

 

위의 조건들을 모두 고려해서 문제를 해결하면 된다.

 

-시간복잡도-

정렬 O(NlogN), 계산로직이 O(N) 이되기떄문에 O(NlogN)이 된다.

 

-코드-

#include <algorithm>
#include<iostream>
#include<vector>
using namespace std;

vector<int> p,m;
bool zero=false;
int n,result=0;

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

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int data;
        cin>>data;
        if(data<0) m.push_back(data);
        else if(data==0) zero=true;
        else p.push_back(data);
    }
    sort(p.begin(),p.end(),compare);
    sort(m.begin(),m.end());
    for(int i=0;i<p.size();i++){
        if(i+1<p.size()){
            if(p[i]==1||p[i+1]==1){
                result+=p[i]+p[i+1];
            }
            else{
                result+=p[i]*p[i+1];
            }
            i++;
        }
        else{
            result+=p[i];
        }
    }
    for(int i=0;i<m.size();i++){
        if(i+1<m.size()){
            result+=m[i]*m[i+1];
            i++;
        }
        else{
            if(!zero){
                result+=m[i];   
            }
        }
    }
    cout<<result;
}