[백준(baekjoon) 1744] 수 묶기

문제

백준 1744

길이가 N(1…10000)인 수열이 주어질 때,
그냥 더 하거나 두 수 씩 묶어 곱한 후 더한 값이 최대가 되는 경우를 찾아 최대 값을 출력하시오.

• 주의 : 자신과 자신은 곱할 수 없으며, 이미 한번 묶인 수는 재 이용될 수 없다.
• 예시 : {0, 1, 2, 4, 3, 5}일 때, 최대 값 = 0 + 1 + (2 * 3) + (4 * 5) = 27

해결

알고리즘

그리디 알고리즘을 사용해 해결하였다.
최적이 되는 순간이 어떤 경우인지 파악하였다.

그리디 알고리즘에 대해 잘 모르신다면 이 글을 참고하세요!

설명

간단히 최대 값이 되기 위해선 어떤 조건이 있어야 할지 생각해보았다.

1. -는 -와 묶여 양수가 되어야 한다. 혹은, 0과 묶여 0이 되어야 한다.
2. 같은 부호 끼리 묶인 경우, 각 절대 값의 크기가 클수록 커진다.
3. 1은 묶이지 않고 그냥 더 할 때, 최종값이 1 커진다.

조건들을 고려해 문제를 해결해보았다.
우선 1, 2번 조건을 고려해 오름차순으로 배열을 정렬하였다.
이로써 부호가 같고, 절대 값이 큰 값 끼리 쉽게 묶을 수 있게 되었다. 

그리고 1번에 따라 0은 음수와 묶여야 하므로, 0보다 같거나 작은 최대 인덱스 값을 구해 저장해두고,
음수는 가장 작은 값 부터(=절대값이 큰 음수), 양수는 가장 큰 값 부터 접근해 두개씩 묶어 주었다.
그리고 하나씩 남는 값들은 그냥 더 해주고, 1의 경우 예외처리로 그냥 더해주었다.

구현 java

1.import java.util.*;
2.
3.public class Main {
4.    public static void main(String[] args) {
5.        Scanner sc = new Scanner(System.in);
6.        int n = sc.nextInt();
7.        int[] input = new int[n];
8.
9.        // 음수(여기선 0 포함)와 양수를 구분하기 위한 index
10.        int minusCnt = 0;
11.        for (int i = 0; i < n; i++) {
12.            input[i] = sc.nextInt();
13.            if (input[i] <= 0) minusCnt++;
14.        }
15.
16.        Arrays.sort(input);
17.        int i = -1;
18.        int answer = 0;
19.
20.        while (++i < minusCnt) {
21.            if (i + 1 < minusCnt) answer += input[i] * input[++i];
22.            else answer += input[i];
23.        }
24.
25.        i = n;
26.        while (--i >= minusCnt) {
27.            if (i - 1 >= minusCnt && input[i - 1] > 1)
28.                answer += input[i] * input[--i];
29.            else answer += input[i];
30.        }
31.        System.out.println(answer);
32.    }
33.}

결과