• 백준 1744번 수 묶기 :: 마이구미
    알고리즘 풀이/그리디 2017. 9. 18. 20:59

    이 글은 백준 알고리즘 문제 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


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    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] < && array[left + 1< 1) {
                ans += array[left] * array[left + 1];
            } else {
                break;
            }
        }
        // +
        for (; right > 0; right -= 2) {
            if (array[right] > && array[right - 1> 1) {
                ans += array[right] * array[right - 1];
            } else {
                break;
            }
        }
     
        for (; right >= left; right--) {
            ans += array[right];
        }
        System.out.println(ans);
    }
    cs


    댓글 0

Designed by Tistory.