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

---

처음 문제를 읽고는 엥? 이게 왜 골드지...? sort하고 0이 아닌 양수 음수 각각 절대값이 큰 수부터 묶어나가면서 계산하면 되지 않나? 라는 생각을 하였다.

(설마 출력이 2^31이라고 int 써서 통과 못하는 사람들이 생겨서 그런가 했다. 묶었을 때 2^31보다 커진 후 음수를 빼며 int 범위 내로 돌아갈 수 있는 걸 낚는 낚시인가 싶었다.)

 

운이 좋게도 예제 4번이 반례가 되어 -1 0 1 인 경우를 해결하지 못했다. 이 경우(-1 0) + 1 로 풀어야 하는데 내 알고리즘은 그렇지 못했다.

추가적으로 -5 -4 -1 0 5 10이라는 테스트 케이스를 생성한 후 고민해보았는데

 

양수 음수를 나눠서 양쪽으로 묶는 행위를 진행해야겠다 라는 생각이 들었다. 그런데 투 포인터로 설계하기에는 다소 어려움이 있었고 시간도 2초에 N도 작겠다 그냥 2개의 배열로 받아서 처리해야겠다는 생각이 들었다.

 

이후 구현하였는데 3가지를 놓치고 있었다.

1. vector.size()는 unsigned int라서 0보다 작은 경우 2^64 - 1 의 값이 들어간다는 점
2. -124 124 0 0 과 같이 0이 여러개 들어가서 계산을 복잡하게 할 수 있다는 점
3. 1과 곱하는 것보다 더하는 게 더 큰 수가 된다는 점

이 두가지였는데, 전체 코드를 바꾸기 귀찮아서 0을 체크해주는 flag를 세우고 1번만 0을 넣도록 하였다. 어차피 0은 더하나 빼나 0이고 우리가 0을 곱하는 경우는 남은 음수값을 지우기 위해서인데, 남은 음수라는 것부터가 2개씩 묶고 나면 1개뿐이기 때문이다.

---

#include <bits/stdc++.h>
using namespace std ;
long long int answer ;
int N, has_zero ;

int main()
{
    ios::sync_with_stdio(0), cin.tie(0) ;
    cin >> N ;
    vector<int> vec(N), positive, negative ;

    for(int &it : vec)
    {
        cin >> it ;
        if(it == 0)
        {
            has_zero = 1 ;
            continue ;
        }
        it > 0 ? positive.push_back(it) : negative.push_back(it) ;
    }

    sort(positive.begin(), positive.end()) ;
    sort(negative.begin(), negative.end()) ;
    if(has_zero) negative.push_back(0) ;

    for(int i = positive.size() - 1 ; i > 0 ; i-=2)
    {
        if(positive[i] == 1 || positive[i-1] == 1) answer += positive[i] + positive[i-1] ;
        else answer += positive[i] * positive[i-1] ;
    }
    
    for(int i = 0 ; i < (int)negative.size() - 1 ; i+=2)
        answer += negative[i] * negative[i+1] ;

    if(positive.size() & 1) answer += positive[0] ;
    if(negative.size() & 1) answer += negative[negative.size() - 1] ;
    cout << answer ;
}

---

느낀점: 조건 분기라고 많은 조건이 들어가지는 않지만 다뤄야할 경우를 포괄하는 좋은 코드를 짜는게 어려운 일 인 것 같다.

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

1744번: 수 묶기