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

안녕하세요! 오늘은 BOJ 1744 - 수 묶기 문제를 풀어볼게요.

 

문제를 읽어보면, 길이가 N인 수열에서 위치에 상관없이 두 수를 묶을 수 있고, 묶은 두 수는 곱해서 더한다고 해요.

자기 자신을 묶을 수는 없고, 수열의 모든 수는 단 한 번만 묶거나, 묶지 않아야 하고, 이렇게 각 수를 적절히 묶었을 때 합이 최대가 될 때의 합을 구하고 싶대요.수열의 크기 N은 50 이하의 자연수고, 수열의 수가 -1000부터 1000까지니까 아무리 최대한 큰 수끼리 묶어서 더한다고 해도 1000 * 1000 * 25 = 25,000,000 이니까, 정수형 범위 안에 들어옴이 보장되어 있어요.

 

접근

 

 

먼저 문제에서 준 예시부터 살펴볼게요.수열 {0. 1. 2. 4. 3. 5}에서 그냥 더하면 0+1+4+3+5 = 15인데, 2와 3, 4와 5를 묶어주면, 0+1+(2*3)+(4*5)=27로 최대가 되네요.그냥 더하는 건 당연한 결과고, 묶어서 최대를 구할 때 식의 형태를 봤을 때 무언가... 정렬이 되어있다는 느낌이 드네요?

 

이것을 캐치했다면 이 문제를 다 푼 거나 다름없는 게,이 문제의 핵심은 정렬과 부호에 따른 케이스분류에요.이제 구현을 하기 전 자잘한 케이스 분류를 조금 더 해볼게요.

 

합을 최대로 만들어야 하는데, 원소가 양수인 경우를 먼저 살펴볼게요.내림차순으로 정렬해서 양수는 양수끼리 큰 수부터 묶는 것이 합을 최대로 만들 수 있어요.

 

그런데 1은 예외예요.양수와 1을 묶게 되면 오히려 합이 작아지게 돼요.2*1=2니까, 2+1=3보다 작아지게 되고, 1*1=1이니, 1+1=2보다 작아지게 돼요.그러니 1은 묶을 숫자로 포함해서는 안돼요.  0의 경우에는 양수와 묶으면 곱이 0이 되어버리니 무조건 손해가 되겠죠?

 

 

다음으로 원소가 음수인 경우를 살펴볼게요.

음수와 음수를 곱하면 양수가 나오니, 음수를 오름차순으로 정렬해서 음수는 음수끼리 작은 수부터 묶는 것이 합을 최대로 만들 수 있어요. (음수는 절댓값이 클수록 작은 값이기 때문이에요.)

 

음수와 양수를 묶는 것은 음수와 양수를 곱하면 음수가 되니 오히려 합이 작아지게 되므로 손해예요.

그리고 0을 묶는 경우는 잘 살펴봐야 하는 게, 음수인 원소의 개수가 홀수일 경우에는 작은 수부터 묶다가 마지막에 남은 음수를 0이랑 묶어야 합을 최대로 만들 수 있어요. (최솟값부터 묶으니 마지막에 남은 음수는 음수 중에서는 최댓값이겠네요.)

예를 들어, {-6, -3, -2, 0}과 같은 수열에서는 최솟값부터 묶으면 {(-6) * (-3)} + {(-2) * 0}인 경우가 최대가 되겠죠?

 

구현

 

#include <iostream>
#include <algorithm>
using namespace std;
int arr[51];
bool isused[51];

int main(void) {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) cin >> arr[i];

    if (n == 1) { // 원소가 1개일 경우 예외처리.
        cout << arr[0];
        return 0;
    }

    sort(arr, arr+n);

    int result = 0;

    for (int i = 0; i < n - 1; i++) { // 원소가 음수인 경우 최솟값부터 묶는 것이 이득
        if (arr[i] < 0) { // 이번 수가 음수일 경우
            if (arr[i+1] <= 0) { // 다음 수가 음수거나 0이면
                result += arr[i] * arr[i+1]; // 묶는 것이 이득!
                isused[i] = true;
                isused[i+1] = true;
                i++;        
            }
            else { // 다음 수가 양수일 경우
                result += arr[i]; // 안묶는 것이 이득!
                isused[i] = true;
            }
        } 
        else if (arr[i] == 0) {
            result += arr[i]; // 이번 수가 0일 경우 다음 수는 0 아니면 양수이므로 묶지 않고 그냥 더하는 것이 이득
            isused[i] = true;
        }

        else if (arr[i] > 0) break; // 이번 수가 양수일 경우 반복문 탈출
    }

    for (int i = n - 1; i >= 1; i--) { // 원소가 양수인 경우 최댓값부터 묶는 것이 이득
        if (arr[i] <= 0) break; // 이번 수가 0이거나 음수인 경우는 이미 위 for문에서 결과에 반영했으므로 반복문 탈출
        else {
            if (arr[i-1] <= 1) { // 이전 수가 음수거나 0이거나 1이면 묶지 않는 것이 이득!
                result += arr[i];
                isused[i] = true;
            } else { // 이외의 경우에는 묶는 것이 이득!
                result += arr[i] * arr[i-1];
                isused[i] = true;
                isused[i-1] = true;
                i--;
            }
        }
    }

    for (int i = 0; i < n; i++) { // 사용하지 못한 원소는 묶지 못한 원소이므로 그냥 더함
        if (!isused[i]) result += arr[i];
    }

    cout << result;
    return 0;
}

 

풀이를 더 깔끔하게 하려면, 양수를 담는 벡터와 0과 음수를 담는 벡터를 나누고 각각 오름차순 정렬, 내림차순 정렬하는 것이 좋겠지만, 하나의 배열만 사용하고 오름차순 정렬만 하도록 구현해서 다소 복잡하네요.

 

먼저 수열을 배열로 받아주고 오름차순 정렬을 한 번만 했어요.

최솟값은 0번째 인덱스에 있을 거니까, 음수인 경우부터 살펴보도록 했는데, i번째 인덱스도 음수이고 i+1번째 인덱스도 음수이거나 0이라면 서로 묶어야 하니까 result에 두 수를 곱해서 값을 저장해 줘요.

이때 0이 포함된 이유는, 오름차순 정렬이 되어있으니 0이 다음 값이라는 것은 음수 중에서 모든 음수를 묶었고, 마지막으로 남은 음수라는 뜻이기 때문이에요.

그리고 i+1번째 인덱스는 이미 사용했으니 i+2번째 인덱스를 다음에 탐색할 수 있도록 i++을 해주었어요.

0일 경우는 그냥 더하나 마나 의미는 없지만, 의미를 분명히 하기 위해 더해주도록 했고, 양수가 나오기 시작하면 반복문을 탈출해요.

 

이번에는 양수를 처리할 텐데, 양수는 최댓값부터 묶는 것이 합이 최대가 되니까, n-1번째 인덱스부터 거꾸로 for 반복문을 돌 거예요.

i번째 인덱스의 값이 0 이하인 경우는 이제 양수를 다 처리했다는 의미고, 0 이하의 값은 이미 앞 for문에서 처리를 했기 때문에 반복문을 탈출하면 돼요.

그 외의 경우에서는 i번째 인덱스의 값과 i-1번째 인덱스의 값을 묶을 텐데, i-1번째 인덱스의 값이 만약 1 이하이면 앞서 살펴봤듯이 묶는 것이 손해가 되니 그냥 result에 i번째 인덱스의 값을 더해줘요.i-1번째 인덱스의 값이 1이 아닌 양수라면 그냥 묶는 것이 최대이니 result에 두 수를 곱해서 값을 저장해 주는 것으로 구현했어요. 

 

그리고 마지막 for문이 필요한 이유는, {1, 1}과 같이 입력이 들어왔을 때 아래 for문에서 1번째 원소인 1만 result 변수에 더하고 반복문을 빠져나오게 돼요.

따라서 마지막에 혹여나 묶이지 않고 결과에 더하지 않은 원소가 남아있는지 확인하고 더해주기 위해서예요.