[백준/C++] 알고리즘 1744번 - 수 묶기

안녕하세요! 테크지니어22입니다.

오늘은 백준 알고리즘 1744번 - 수 묶기를 풀어보도록 하겠습니다.

 

 

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

 

[문제 접근]

n은 50이하이고 시간 제한은 2초여서 시간에 얽매이지 않고 생각했습니다.

수를 적절히 묶었을 때의 합이 최댓값을 구해야하기 때문에 적절히 묶는 방법이 무엇일까를 고민하는 그리디 알고리즘이었습니다.

예제를 살펴보면서 적절히 묶는 조건을 고려했습니다.

 

적절히 묶는 조건

- 큰거끼리 곱할수록 커집니다.

- 음수는 음수끼리 곱해야합니다.

- 1은 무조건 더해야합니다. 

- 음수의 개수가 홀수이면 가장 큰 음수를 0이 존재하면 곱해서 없애고 0이 없으면 결과값에 더합니다.

 

[풀이 전략]

1. 양수와 음수를 각각 벡터에 저장합니다.

2. 0이 존재하면 zeroflag를 true로 바꿔줍니다.

3. 양수 벡터는 내림차순으로, 음수 벡터는 오름 차순으로 정렬합니다.

4.양수의 개수가 홀수이면 가장 작은 양수를 결과값에 더하고 벡터에서 pop합니다.

5. for문을 활용하여 양수를 저장하는 벡터를 두 칸 건너뛰면서  묶은 수를 곱한 후 결과값에 더합니다. 이 때 만약 1이 하나라도 존재하면 결과값에 모두 더합니다.

6. 음수의 개수가 홀수이면 가장 큰 음수를 0이 존재하면 곱해서 없애고 0이 없으면 결과값에 더하고 벡터에서 pop합니다

7.  for문을 활용하여 음수를 저장하는 벡터를 두 칸 건너뛰면서  묶은 수를 곱한 후 결과값에 더합니다. 

8. result를 출력합니다.

 

[코드]

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


int n ; 

vector<int> v1; // 양수
vector<int> v2; // 음수
bool zeroflag = false ;
int result ;
vector<int> v ;
int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    cin >> n ; 
    for(int i = 0 ; i< n ; i++)
        {   int tmp ;
            cin >> tmp ;
            if(tmp == 0) zeroflag = true;
            else if(tmp > 0) v1.push_back(tmp);
            else v2.push_back(tmp);
        }
    
    sort(v1.begin(),v1.end(),greater<int>());
    sort(v2.begin(),v2.end());

    if(v1.size() % 2 == 1){
        result += v1.back();
        v1.pop_back();
    }
    if(v1.size() != 0) {
        for(int i = 0 ; i < v1.size()-1 ; i+=2){
        if(v1[i] == 1 || v1[i+1] == 1) result+= v1[i]+v1[i+1];
        else 
        result += v1[i]*v1[i+1];
    } }
    
     if(v2.size() % 2 == 1){
        if(!zeroflag) result += v2.back();
        v2.pop_back();
    }
    if(v2.size() != 0) {
        for(int i = 0 ; i < v2.size()-1 ; i+=2){
        result += v2[i]*v2[i+1];
    } }
    
    cout<< result ; 
}

[배울 점]

- 정렬할 때 음수의 대소 순서 주의하기

- for문의 루프조건에서 v.size()-1을 조심하기 -> v.size()는 unsigned int이기 때문에 만약 이 값이 0이고 0-1을 하면 4294967295값이 나옴.