[백준] 1744번: 수 묶기 | C++

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

1744번: 수 묶기

 

틀린 이유

1. 음수 벡터를 내림차순으로 정리하지 않았다. 음수와 양수 벡터에서 절댓값이 큰 값 2개를 곱하는 것으로 접근하였는데, 음수 벡터도 오름차순으로 정리하여 절댓값이 작은 값부터 pop_back() 되었다.

ex) [-1, -23, -6, -72] => [-72, -23, -6, -1], v.back() == -1

 

2. 양수 벡터와 음수 벡터에 원소가 1개씩 남았을 때, zeroCnt가 0일 때 코드 구현을 하지 않았다.

zeroCnt가 1이상일 때 음수와 0을 곱해 상쇄시키고 양수를 더한다. 수열에 0이 없었을 때는 음수*양수보다 음수+양수가 무조건적으로 크다 생각하여 answer에 더한다.

 

 

정답코드

분기점이 많아 각 분기점에서 다르게 탐욕적으로 접근해야 하는 게 관건이었다.

양수와 음수로 따로 벡터에 저장하고 각 벡터의 원소가 2개 이상 남아있으면 곱하여 더한다. 

0은 더하기에 영향을 주지 않고 음수를 상쇄하는 데에만 사용이 되기 때문에 zeroCnt를 int로 선언하지 않고 bool로 선언하여도 될 것 같다.

 

출력이 2^31 미만이므로 int 자료형으로 표현 가능한 범위이다.

#include<iostream>
#include<vector>
#include<algorithm>
#define fse(A,B,C) for(int i=A;i<B;i+=C) 
using namespace std;
int N;
vector<int> positive;
vector<int> negative;
int zeroCnt;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>N;
    fse(0,N,1) {
        int tmp;
        cin>>tmp;
        if(tmp==0) {
            zeroCnt++;
            continue;
        }
        if(tmp>0) positive.push_back(tmp);
        else negative.push_back(tmp);
    }

    sort(begin(positive),end(positive));
    sort(begin(negative),end(negative),greater<int>()); //내림차순
    int answer=0;
    while(positive.size()>=2){
        int fst=positive.back();
        positive.pop_back();
        int snd=positive.back();
        positive.pop_back();

        if(snd!=1){
            answer+=fst*snd;
        }else{
            answer+=fst+snd;
        }
    }
    while(negative.size()>=2){
        int fst=negative.back();
        negative.pop_back();
        int snd=negative.back();
        negative.pop_back();
        
        answer+=fst*snd;
    }

    if(!positive.empty() && negative.empty()){
        answer+=positive.back();
    }
    else if(positive.empty() && !negative.empty()){
        if(zeroCnt>0) zeroCnt--;
        else answer+=negative.back();
    }
    else if(!positive.empty() && !negative.empty()){
        if(zeroCnt>0){
            zeroCnt--;
            answer+=positive.back();
        }else{
            answer+=positive.back()+negative.back();
        }
    }
    cout<<answer;
}

 

 

비슷한 문제(동일 문제?)

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

2036번: 수열의 점수

하나의 코드로 두 문제 제출 가능...! 일석이조ㅎㅎ