문제

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

이해

주어진 수열에 대해서 전체 합을 구해야 한다. 단, 수 2개를 하나로 묶을 수 있다. 묶은 수들은 서로를 곱해서 새로운 값으로 치환할 수 있다.

위치 상관없이 2개의 수를 묶을 때 사용할 수 있다.

접근

문제를 잘 읽고 유형을 파악하는게 중요한 문제인 것 같다. 초기에 인접한 수만 묶을 수 있는 줄 알고 DP로 풀려고 했지만 뻘짓이었다..

묶는 수는 위치와 관계가 없다. 우리는 조건에 따른 합의 최대를 구해야 하기 때문에 최대가 될 때는 어떻게 묶이는게 좋은가에 대해서 생각하면 된다.

[0, 1, 2, 3, 4, 5]라는 수를 묶어보자. 당연하게도 (5, 4), (3, 2), (1), (0)으로 묶어 최대가 27이라는 것을 알 수 있다. 규칙이 보이지 않는가? 바로 곱셈을 최대로 하기 위해 큰 수끼리 묶으면 되는 것이다.

[음수에 대해]

그렇다면 단순히 정렬해서 묶으면 될까? 그렇지 않다. 본 문제는 음수까지 입력으로 받을 수 있다. 음수x음수는 양수가 된다. 따라서 음수는 음수끼리 곱하는 것이 최대가 될 수 있겠다. 그렇다면 음수 역시 양수처럼 큰 수끼리 묶는 것이 유리하다. 정확히는 음수의 경우 절댓값이 큰 수끼리 묶는 것이 유리하다.

[0, 1, -1에 대해]

분기처리할 때 위와 같은 수를 조심해야 한다. 위에서 부호가 같은 수끼리 곱하는 것이 유리하다고 했지만 1의 경우는 그렇지 않다. (3, 1) 보다 (3), (1)이 크지 않는가? 그렇다. 1은 그냥 더하는 것이 최대가 되게 한다.

-1은 어떨까? -1은 부호를 바꿀 수 있는 힘이 있다. 그래서 같은 음수끼리 곱했을 때 양수로 변환해 최대가 될 수 있게 한다. 곱하는 것이 유리하다.

0이 가장 독특하다고 할 수 있다. 0은 언뜻보면 아무 의미가 없어보이지만 음수랑 곱했을 때 0으로 치환할 수 있다는 장점이 있다. 따라서, 우리가 마지막 남은 음수가 있을 때 0도 가지고 있다면 서로를 곱해 0으로 치환하는 것이 좋다.

지금까지 분기조건에 대해서 정리해보았다. 아래 코드를 보면서 이해해보자.

풀이

    static Comparator<Integer> absComp = new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return Math.abs(o2) - Math.abs(o1);
        }
    };

정렬조건은 절댓값을 기준으로 했다.

        int ans = 0;
        int pBuffer = 0;
        int mBuffer = 0;
        boolean flag = false;

        for (int i = 0; i < arr.size(); i++) {
            int n = arr.get(i);

            if (n == 0) {
                flag = true;
                continue;
            } else if (n == 1) {
                ans++;
                continue;
            } else if (n > 1) {
                if (pBuffer > 0) {
                    ans += (pBuffer * n);
                    pBuffer = 0;
                } else if (pBuffer == 0) {
                    pBuffer = n;
                }
            } else {
                if (mBuffer < 0) {
                    ans += (mBuffer * n);
                    mBuffer = 0;
                } else if (mBuffer == 0) {
                    mBuffer = n;
                }
            }
        }

필자는 buffer를 활용했다. pBuffer는 양수버퍼, mBuffer는 음수버퍼를 의미한다. 각 부호에 해당하는 수를 저장해놓았다가 이후 검사에 같은 부호를 만나면 곱하고 초기화하는 방식이다. 물론, 스택을 활용해도 된다.

0은 1개 여부만 파악하면 되기 때문에 boolean형을 활용했다.

분기조건에 대해서 보자. 1인 경우에는 그냥 더했다. 1보다 클 때 혹은 음수일 때는 각각의 버퍼를 확인해서 분기처리를 했다.

        if (pBuffer != 0) {
            ans += pBuffer;
        }
        if (mBuffer != 0) {
            if (!flag) {
                ans += mBuffer;
            }
        }

마지막으로 남은 버퍼를 처리하면 된다. 양수는 그냥 더하면 되고 음수는 수열에 0이 있는지 보고 있다면 0으로 치환하고 없다면 그냥 수를 더한다.

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class App {
    static int N;
    static List<Integer> arr;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        arr = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            arr.add(Integer.parseInt(br.readLine()));
        }

        Collections.sort(arr, absComp);

        int ans = 0;
        int pBuffer = 0;
        int mBuffer = 0;
        boolean flag = false;

        for (int i = 0; i < arr.size(); i++) {
            int n = arr.get(i);

            if (n == 0) {
                flag = true;
                continue;
            } else if (n == 1) {
                ans++;
                continue;
            } else if (n > 1) {
                if (pBuffer > 0) {
                    ans += (pBuffer * n);
                    pBuffer = 0;
                } else if (pBuffer == 0) {
                    pBuffer = n;
                }
            } else {
                if (mBuffer < 0) {
                    ans += (mBuffer * n);
                    mBuffer = 0;
                } else if (mBuffer == 0) {
                    mBuffer = n;
                }
            }
        }

        if (pBuffer != 0) {
            ans += pBuffer;
        }
        if (mBuffer != 0) {
            if (!flag) {
                ans += mBuffer;
            }
        }

        System.out.println(ans);
    }

    static Comparator<Integer> absComp = new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return Math.abs(o2) - Math.abs(o1);
        }
    };
}

결과