[JAVA]수 묶기(Baekjoon)

문제

문제

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

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

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

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

입력

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

출력

 수를 합이 최대가 나오게 묶었을 때 합을 출력한다. 정답은 항상 $2^{31}$보다 작다.

예제 입력 1

4
-1
2
1
3

예제 출력 1

6

예제 입력 2

6
0
1
2
4
3
5

예제 출력 2

27

예제 입력 3

1
-1

예제 출력 3

-1

예제 입력 4

3
-1
0
1

예제 출력 4

1

예제 입력 5

2
1
1

예제 출력 5

2

풀이

 수학 문제이다. 경우를 나눠 본다면 다음과 같다. 양수의 경우, 음수의 경우.
 양수의 경우에는, 수를 큰 수부터 다음으로 큰 수와 곱하여 합산하였을 경우 가장 크다.
 음수의 경우에는, 가장 작은 수(절대값이 가장 큰 수)부터 다음으로 작은 수를 곱하여 합산하였을 경우 가장 크다. 음수의 개수가 홀수이고, 수열에 0이 포함되어 있다면, 절대값이 가장 작은 음수를 0과 곱하여 합산한다.

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        for(int i = 0; i < N; i++)
            arr[i] = Integer.parseInt(br.readLine());
        Arrays.sort(arr);
        int sum = 0;
        int idx = 0;
        // idx-1 까지가 음수의 범위
        while(true){
            if(arr[idx] >= 0 || idx+1 >= N)
                break;
            idx++;
        }
        int i = 0;
        for(; i < idx - 1; i += 2){
            sum += arr[i] * arr[i+1];
        }
        if(i == idx - 1 && arr[idx] != 0 || i == idx && arr[idx] < 0)
            sum += arr[i];
        // idx부터 끝까지 양수의 범위(1은 제외) : 1은 양수에 곱해도 그대로이기 때문에 그대로 더하는것이 더 큰 합을 만듦
        while(true){
            if(idx+1 > N || arr[idx] > 1)
                break;
            idx++;
        }
        for(i = N - 1; i > idx; i -= 2){
            sum += arr[i] * arr[i-1];
        }
        i = idx - 1;
        while(true){
            if(i < 0)
                break;
            if(arr[i] > 0)
                sum += arr[i--];
            else
                break;
        }
        System.out.println(sum);

 처음 생각했던대로 문제를 풀었는데, 테스트 케이스는 맞다고 나오나 제출 시 틀렸다고 나왔다. 조건들을 부가적으로 달아보고, 수정해보아도 결과는 똑같아서 결국에 찾아보고 풀었다.

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static List<Integer> nn = new ArrayList<>();
    static List<Integer> pn = new ArrayList<>();
    public static void main(String[] args) throws Exception{
        int N = Integer.parseInt(br.readLine());
        for(int i = 0; i < N; i++){
            int n = Integer.parseInt(br.readLine());
            if(n > 0)
                pn.add(n);
            else
                nn.add(n);
        }
        //리스트 정렬
        Collections.sort(pn, Collections.reverseOrder());
        Collections.sort(nn);

        int sum = 0;
        int i = 0;
        //양수의 경우
        while(i < pn.size()){
            if(i + 1 < pn.size() && pn.get(i) != 1 && pn.get(i+1) != 1)
                sum += pn.get(i++) * pn.get(i++);
            else
                sum += pn.get(i++);
        }
        i = 0;
        //음수의 경우
        while(i < nn.size()){
            if(i + 1 < nn.size() && nn.get(i) != 1 && nn.get(i+1) != 1)
                sum += nn.get(i++) * nn.get(i++);
            else
                sum += nn.get(i++);
        }
        System.out.println(sum);
    }
}

 찾아본 알고리즘은 두개의 리스트를 만들어, 양수 리스트와 음수 리스트로 둔다. 그리고, 양수 리스트는 내림차순으로 정렬한다. 그리고, 두개씩 원소를 꺼내 곱하여 합산하고, 하나가 남았을 경우에는 그냥 더한다.
 음수 리스트의 경우에도 두개씩 꺼내어 곱하여 합산하고, 하나가 남았을 경우에는 그냥 더한다.
 사실 리스트를 나눠하면 매우 간단한 문제인데, 메모리를 생각하여 하나로만 해결하려고 하는 습관때문에 쓸데없이 시간낭비를 한 것 같다. 메모리를 조금 더 쓰더라도, 훨씬 간단하고 쉬워진다면 이 방향이 나은 거 같다.