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

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

1744번: 수 묶기

1. 주의할 점

- 음수/0/양수로 나눈다

- 음수의 경우, 0과 관련지어서 생각한다

- 양수의 경우, 1일 때 조건을 추가한다

 

2. 구현 (이해가 안되는 부분은 코드에 주석을 달았으니 확인 바람)

- 수를 입력 받을 때, 음수인 경우 M에 양수인 경우 P에 추가한다. 0인 경우, Zero++를 수행한다

- 음수의 경우 오름차순으로, 양수는 내림차순으로 정렬한 이후, 음수->0->양수 순서대로 Arr[] 배열에 담는다

- Arr[] 모든 배열을 For문을 통해 현재 값을 Cur, 다음 값을 Next에 할당한다

- 만약 Cur이 음수이며, 다음 수가 존재할 경우 Next를 확인한다. 이때, Next가 음수라면 Cur*Next를 Result에 더한다(음수*음수=양수). Next가 0이라면 둘이 곱한 0이 더했을때(음수)보다 크므로 곱한 후, 더한다고 가정한다. 만약 Next가 양수라면 Cur를 Result에 더한다

- 다음 수가 없다면 그대로 Result에 더한다

- Cur이 0이면 건너뛴다

- Cur이 양수면, 1인지 확인한다. 1이라면 Result에 1을 더한다. (Result + 1*Next <= Result 1+Next가 성립하기 때문)

- 1이 아니라면, 다음 수가 있는지 확인한다. 다음수가 없다면 그대로 더하고, Next가 존재하면 곱한 이후 더한다

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> m,p;
int arr[10001];

int main() {
    int num,result=0,cur,next,zero=0,a;
    cin>>num;
    for(int i=0;i<num;i++){
        cin >> a;
        if(a<0)
            m.push_back(a);
        else if(a>0)
            p.push_back(a);
        else
            zero++;
    }
    sort(m.begin(),m.end());
    sort(p.begin(),p.end(),greater<int>());
    int idx=0;
    for(int i=0;i<m.size();i++)
        arr[idx++]=m[i];
    for(int i=0;i<zero;i++)
        arr[idx++]=0;
    for(int i=0;i<p.size();i++)
        arr[idx++]=p[i];
    for(int i=0;i<num;i++){
        cur = arr[i];
        if(cur<0){
            if(i+1<num){        //다음 수가 있는 경우
                next = arr[i+1];
                if(next==0)    //cur*next=0, result+=0 => result
                    i++;
                else if(next<0){
                    i++;
                    result+=(cur*next);
                }
                else   //next>0
                    result+=cur;
            }
            else           //다음 수가 없는 경우
                result+=cur;
        }
        else if(cur > 0){       //1인 경우 예외 존재 2*1보다 2+1이 더 큼
            if(cur==1){
                result+=1;
                continue;
            } 
            if(i+1<num){        
                next = arr[i+1];
                if(next==1)
                    result+=(next+cur);
                else
                    result+=(cur*next);
                i++;
            }
            else
                result+=cur;
        }
    }
    cout<<result;
    return 0;
}