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

 

 

 

알고리즘 종류

    - 정렬

 

 

 

사고 과정

    - 음수와 양수일 때를 나눈다.

    - 음수의 경우, 1보다 작은 수는 무조건 곱하면 총합이 커진다. 둘 다 음수인 경우, 곱하면 양수가 된다. 하나는 음수 하나는 0일 경우에는 음수 값이 사라지기 때문에 총합이 커진다.

    - 양수의 경우, 1보다 큰 수는 무조건 곱하면 총합이 커진다. 둘 다 양수일 경우, 곱하면 더 커진다. 하나가 1보다 큰 양수이고 나머지 하나가 1일 경우, 총합이 1작아진다. 2 * 1 = 2이고, 2 + 1 = 3이기 때문이다. 마찬가지로 하나가 0일 경우에 2 + 0 = 2, 2 * 0 = 0 임을 알 수 있다.

 

 

 

구현(C++)

#include <vector>
#include <iostream>
#include <algorithm>
 
 
using namespace std;
 
int n;
int total = 0;
vector<int> v;
 
int main(){
    
    cin >> n;
    
    for(int i=0; i<n; i++){
        int num;
        cin >> num;
        v.push_back(num);
    }
    
    sort(v.begin(), v.end());
    int left = 0, right = n-1;
    
    // 음수일 때
    for(left; left<n-1; left+=2){
        if(v[left] < 1 && v[left+1] < 1){
            total += v[left] * v[left+1];
        }
        else break;
    }
    
    // 양수 일 때
    for(right; right>0; right-=2){
        if(v[right] > 1 && v[right-1] > 1){
            total += v[right] * v[right-1];
        }
        else break;
    }
    
    // 위 두 경우에서 남은 숫자 처리
    for(left; left<=right; left++){
        total += v[left];
    }
    
    cout << total << endl;
    
}

 

 

 

시행착오

    - 괜히 어려울 것 같아서 제 발 저리다가 나열해서 보니 범위만 잘 설정해 주면 쉬웠다.

    - left와 right 변수를 이용해서 위치를 나타내는 방법은 다른 블로그에서 얻은 아이디어이다. two pointer를 사용하는 것 같은 느낌을 준다. 괜찮은 방법이니 기억해두자.