문제

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

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

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

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

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

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

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

예제 입력 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

접근

이 문제는 탐색을 통해서 결과를 최대로 하는 경우의 수를 찾지 않더라도 그리디하게 접근해서 좀 더 빠르게 최적해를 구할 수 있었다. 큰 수는 큰 수끼리(음수인 경우 작은 수는 작은 수끼리) 묶어서 곱해야 무조건 합이 최대가 되기 때문.

1. 1보다 큰 양의 정수
   : 1보다 큰 양의 정수는 다른 1보다 큰 양의 정수와 곱해야만 숫자를 최대한 크게 만들 수 있다. 0 이하의 정수와 묶어서 곱해 버리면 결과가 0 이하가 되어 버리니 합을 최대로 만들 수 없다. 따라서 함께 묶을 1보다 큰 양의 정수가 더 이상 남아 있지 않다면 묶지 않고 그냥 더해야 최적이다.

2. 0 또는 음의 정수
   : 0 이하의 정수는 다른 0 이하의 정수와 곱해야만 음이 아닌 정수가 된다.
   양의 정수와 묶어서 곱해 버리면 원래 수보다 더 작아질 테니 합을 최대로 만들 수 없다. 따라서 함께 묶을 0 이하의 정수가 더 이상 남아 있지 않다면 묶지 않고 그냥 더해야 최적이다.

3. 1
   : 1을 따로 생각해야 하는 것이 이 문제의 포인트이다.
   1은 어떤 다른 수와 곱하더라도 더할 때보다 값이 작을 수밖에 없다. 심지어 양수와 곱하더라도.
   2 * 1보다 2 + 1이 더 크다는 것을 생각해보자.
   따라서 1의 경우 묶지 않고 그대로 더하는 것이 최적이다.

한 줄로 정리하자면
수열을 정렬한 다음, 0이 나올 때까지는 작은 수부터 2개씩 묶고 1은 묶지 않고 그대로 더하고 그 이후부터는 큰 수부터 2개씩 묶어야 한다.

구현

초기 구현

import java.io.*;
import java.util.Arrays;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        if (N == 1) {
            System.out.println(arr[0]);
            return;
        }
        Arrays.sort(arr);

        int sum = 0;
        int i = N - 1;
        for (; i >= 1 && arr[i] > 1; i -= 2) {
            if (arr[i - 1] > 1) {
                sum += arr[i] * arr[i - 1];
                continue;
            }
            sum += arr[i];
            i++;
        }
        if (i >= 0 && arr[i] > 1) {
            sum += arr[i];
            i--;
        }

        int k = i;
        for (; k >= 0 && arr[k] == 1; k--) {
            sum++;
        }

        int j = 0;
        for (; j < N && j + 1 <= k; j += 2) {
            sum += arr[j] * arr[j + 1];
        }
        if (j < N && arr[j] < 1) {
            sum += (j + 1 == k) ? arr[j] * arr[j + 1] : arr[j];
        }

        System.out.println(sum);
    }
}

접근 방식을 떠올리고도 구현하는 데 꽤 오래 걸렸다..
배열에 있는 연속된 두 값에 동시에 접근해야 하기 때문에 IndexoutOfBounds를 발생시키지 않고 모든 값을 탐색하기 위해 인덱스 값을 조정하는 게 굉장히 머리가 아팠다.
그리고 0 이하의 정수, 1, 1 이상의 정수 사이의 각 경계가 연속적으로 이어져 있으니 관리하기가 어려웠다.

0 이하의 정수와 1 이상의 정수를 별도로 관리

일단 위와 같이 구현한 다음에 찬찬히 생각해 보니, 그냥 0 이하의 정수와 1 이상의 정수를 따로 저장하면 되지 않나...? 라는 생각이 뒤늦게 들었다;;
경계를 따질 필요 없이 아예 분리해서 저장하고 따로 정렬하면 되는 거였다.

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        List<Integer> negative = new ArrayList<>();
        List<Integer> greaterThanOne = new ArrayList<>();
        int sum = 0;
        
        for (int i = 0; i < N; i++) {
            int input = Integer.parseInt(br.readLine());
            if (input == 1) {
                sum++;
            } else if (input > 1) {
                greaterThanOne.add(input);
            } else {
                negative.add(input);
            }
        }

        Collections.sort(negative);
        Collections.sort(greaterThanOne, Collections.reverseOrder());
        
        int i = 0;
        for (; i + 1 < negative.size(); i += 2) {
            sum += negative.get(i) * negative.get(i + 1);
        }
        if (negative.size() % 2 == 1) {
            sum += negative.get(i);
        }

        i = 0;
        for (; i + 1 < greaterThanOne.size(); i += 2) {
            sum += greaterThanOne.get(i) * greaterThanOne.get(i + 1);
        }
        if (greaterThanOne.size() % 2 == 1) {
            sum += greaterThanOne.get(i);
        }

        System.out.println(sum);
    }
}

내가 처음 한 구현보다 시간이 조금 더 걸리긴 했지만 4ms 차이니 그렇게 유의미하지도 않고... 이 코드가 훨씬 직관적이라 더 좋은 코드 같다.

java.util.Iterator를 사용한 최적화

위 코드가 O(N)이라 충분히 빠르고, 심지어 밑에 작성할 풀이도 똑같이 O(N)이라 시간 복잡도에서는 큰 차이가 없지만 다른 분의 코드를 구경하다가 java.util.Iterator를 사용하면 아예 복잡한 인덱스 접근을 생각할 필요가 없다는 걸 알아서 기록해 두려고 한다.

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        List<Integer> negative = new ArrayList<>();
        List<Integer> greaterThanOne = new ArrayList<>();
        int sum = 0;
        for (int i = 0; i < N; i++) {
            int input = Integer.parseInt(br.readLine());
            if (input == 1) {
                sum++;
            } else if (input > 1) {
                greaterThanOne.add(input);
            } else {
                negative.add(input);
            }
        }

        Collections.sort(negative);
        Collections.sort(greaterThanOne, Collections.reverseOrder());
        
		Iterator<Integer> iterator = negative.iterator();
		sum = getSum(iterator, sum);
		
		iterator = greaterThanOne.iterator();
		sum = getSum(iterator, sum);
		
        System.out.println(sum);
    }

    private static int getSum(Iterator<Integer> iterator, int sum) {
		while(iterator.hasNext()) {
			int currentVal = iterator.next();
			
			if (iterator.hasNext()) {
				int nextVal = iterator.next();
				sum += currentVal * nextVal;
			} else {
				sum += currentVal;
			}
		}
		return sum;
	}
}

다음 원소가 존재하는지 여부를 인덱스 값으로 판단하는 대신 iterator.hasNext()로 판단하는 것이다...
이렇게 구현하면 복잡하게 생각할 필요 없이 직관적으로 구현이 가능하다.
이런 거 보면 알고리즘도 알고리즘이지만 java 자체 기능을 잘 숙지하고 활용하는 것도 중요하다 싶다.