[BOJ] 1744 - 수 묶기 JAVA

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은 10,000보다 작은 자연수이다. 둘째 줄부터 N개의 줄에, 수열의 각 수가 주어진다. 수열의 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

출력

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

예제 입력 1

4

-1

2

1

3

예제 출력 1

6

 

 

 

 

 

 

 

풀이 .

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

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> positive = new ArrayList<>();
        ArrayList<Integer> negative = new ArrayList<>();
        boolean hasZero = false;
        int oneCnt = 0;
        for(int i = 0; i < n; i++) {
            int input = Integer.parseInt(br.readLine());
            if(input > 0) {
                if(input == 1) {  // 1은 곱하면 오리혀 손해이므로 따로 개수를 세서 더해준다
                    oneCnt += 1;
                }else {
                    positive.add(input);
                }
            }else if(input < 0) {
                negative.add(input);
            }else {
                hasZero = true;
            }
        }

        // 양수, 음수 각자 절대값의 크기로 내림차순
        Collections.sort(positive);
        Collections.reverse(positive);
        Collections.sort(negative);

        int ans = oneCnt;
        int size = positive.size();
        for(int i = 0; i < size; i+=2) {  // positive
            if(i == size - 1) {  // positive가 홀수개이면 절대값이 가장 작은 것은 그냥 더해줌
                ans += positive.get(i);
            }else {
                ans += positive.get(i) * positive.get(i+1);
            }
        }

        size = negative.size();
        for(int i = 0; i < size; i+=2) {  // negative
            if(i == size - 1) {  // negative가 홀수개이면 절대값이 가장 작은 음수를 0으로 상쇄시킬 수 있는지 확인
                if(!hasZero) {  // 음수를 상쇄시킬 0이 없으면 그냥 음수 더하기
                    ans += negative.get(i);
                }
            }else {
                ans += negative.get(i) * negative.get(i+1);
            }
        }
        System.out.println(ans);
    }
}

 

최대의 합을 만들어내기 위해 양수, 음수, 0을 모두 따로 생각해야 한다.

 

1. 양수일 때

내림차순 정렬하여 절대값이 큰 것 끼리 곱해주면 된다.

홀수개라서 짝이 안 맞을 경우 마지막 원소(= 절대값이 가장 작은 원소)는 그냥 혼자 더해준다.

단, 입력이 1인 경우에는 곱하는 것이 오히려 손해가 된다. 따라서 1의 개수는 따로 세어준 다음 정답 수에 더해준다.

 

2. 음수일 때

오름차순 정렬하여 절대값이 큰 것 끼리 곱해주면 된다.

음수가 짝수개일 경우 모두 짝을 지어 음의 값을 상쇄시킬 수 있다.

만약 홀수개라면 마지막 남은 음수는 0과 묶어서 그 값을 상쇄시켜야 한다. 함께 묶을 0이 없다면 어쩔 수 없이 음의 값을 더해주어야 한다.

 

3. 0일 때

어차피 0은 묶어서 더하든 그냥 더하든 0이다. 총합에 영향을 미치지 않는다.

마지막 하나 남은 음수의 값을 상쇄시켜줄 0이 있는지 없는지만 확인하면 되기 때문에 boolean으로 존재 유무만 체크해주면 된다.