1744번 : 수 묶기

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

1744번: 수 묶기

문제

길이가 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이 되어 최대가 된다.

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

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

 

입력

첫째 줄에 수열의 크기 N이 주어진다. N은 50보다 작은 자연수이다. 둘째 줄부터 N개의 줄에 수열의 각 수가 주어진다. 수열의 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

 

출력

수를 합이 최대가 나오게 묶었을 때 합을 출력한다. 정답은 항상 231보다 작다.

 

---

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        ArrayList<Integer> arr1 = new ArrayList<>(); // 양수 리스트
        ArrayList<Integer> arr2 = new ArrayList<>(); // 음수 리스트
        
        for (int i = 0; i < n; i++) {
            int v = Integer.parseInt(br.readLine());
            if(v>0) arr1.add(v);
            else arr2.add(v);
        }

        int result = 0;
        Collections.sort(arr1, Collections.reverseOrder());
        Collections.sort(arr2);

        // 양수값으로 최댓값 구하기
        Integer pre = null;
        for (int i = 0; i < arr1.size(); i++) {
            if(pre == null) {
                pre = arr1.get(i);
            }
            else {
                if(arr1.get(i) == 1) {
                    result += (pre + 1);
                    pre = null;
                } else { // 수 묶기
                    result += (pre * arr1.get(i));
                    pre = null;
                }
            }
        }
        if(pre != null) {
            result += pre;
            pre = null;
        }

        // 음수값으로 최대값 구하기
        for (int i = 0; i < arr2.size(); i++) {
            if(pre == null) {
                pre = arr2.get(i);
            }
            else {
                // 수 묶기
                result += (pre * arr2.get(i));
                pre = null;
            }
        }
        if(pre != null) {
            result += pre;
        }

        System.out.println(result);
    }
}

 

해결방법

문제는 매우 간단하다. 입력받은 값들로 수를 묶거나 더해서 최댓값을 만들기만 하면 된다.

단순히 오름차순 정렬을 하고 이전 인덱스에 해당하는 값과 현재 인덱스에 해당하는 값을 비교하여 최댓값을 구해야겠다고 생각했다.

하지만 이럴 경우 음수 부분에서 옳지 못한 결과가 나온다.

-1 -2 -3 인 경우 최댓값은 -1 + (-2 * -3) => 5 여야 하는데 위 알고리즘대로면 (-1 * -2) + -3 => -1이 된다.

 

양수의 경우 내림차순 정렬을 하면 5, 4, 3, 2, 1 이기에 이전 인덱스에 해당하는 값과 현재 인덱스에 해당하는 값을 비교하여 최댓값을 구할 수 있는데

음수의 경우 내림차순 정렬을 하면 -1, -2, -3, -4, -5  이기에 이전 인덱스에 해당하는 값과 현재 인덱스에 해당하는 값을 비교하여 최댓값을 구할 수가 없다. 오름차순 정렬을 해야 -5, -4, -3, -2, -1 이 되어 최댓값을 구할 수 있다.

 

결론적으로 양수 리스트와 음수 리스트를 따로 만들어서 양수 리스트는 내림차순 정렬, 음수 리스트는 오름차순 정렬하여 최댓값을 구하는 코드를 작성해야 한다.