백준 1744번 수 묶기 :: 마이구미

이 글은 백준 알고리즘 문제 1744번 "수 묶기" 를 풀이한다.

문제의 접근 방법은 그리디 알고리즘으로써, 어떠한 자료구조를 요구하지는 않는다.

하지만 정답 비율이 낮은 문제로써, 까다로울 수 있다.

1744번 "수 묶기" - https://www.acmicpc.net/problem/1744

그리디 알고리즘 - http://mygumi.tistory.com/121

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 어떤 인접한 원소끼리를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때, 묶은 수는 서로 곱한 후에 더한다.

예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다.

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

수열의 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수

문제만 읽으면 어렵지 않은 문제라고 판단된다.

하지만, 문제를 확실히 이해하지 않는다면, 다양한 반례를 생각하지 못할 수 있다.

대표적인 반례는 다음과 같다.

1. 음수 2개를 곱한다면, 양수가 되기에 최대값을 늘릴 수 있다.

-2 * -3 = 6

2. 음수와 0을 곱하면, 0이 되기에 최대값을 늘릴 수 있다.

-2 * 0 = 0

3. 양수 2개를 곱하면 무조건 최대값을 만들지 않는다.

- 2개중 하나 이상의 수가 1을 포함한다면, 곱한 값보다 더한 값이 크게 된다.

2 * 1 = 2
=> 2 + 1  3

1 * 1 = 1
=> 1 + 1 = 2

본인은 다음과 같이 문제를 해결했다.

음수 => 1보다 낮은 두 수를 곱하면 항상 최대이다.

양수 => 1보다 큰 두 수를 곱하면 항상 최대이다.

우선 입력된 수를 정렬한다.

정렬을 통해 음수와 양수를 나누어 처리할 수 있다.

음수인 경우, 양수인 경우를 무조건 두 수를 통해 최대값을 구해나간다.

그리고 처리되지 못한 수들은 최대의 경우가 없기 때문에 단순히 더하게 된다.

Github - https://github.com/hotehrud/acmicpc

private void solve() {
    int n = sc.nextInt();
    int[] array = new int[n];
    long ans = 0;
 
    for (int i = 0; i < n; i++) {
        array[i] = sc.nextInt();
    }
 
    Arrays.sort(array);
    int left = 0;
    int right = n - 1;
    ans = 0;
    // -
    for (; left < right; left += 2) {
        if (array[left] < 1 && array[left + 1] < 1) {
            ans += array[left] * array[left + 1];
        } else {
            break;
        }
    }
    // +
    for (; right > 0; right -= 2) {
        if (array[right] > 1 && array[right - 1] > 1) {
            ans += array[right] * array[right - 1];
        } else {
            break;
        }
    }
 
    for (; right >= left; right--) {
        ans += array[right];
    }
    System.out.println(ans);
}