백준 2036번 - 수열의 점수

문제

백준 2036번 - 수열의 점수

아이디어

점수가 최대가 되기 위해서는 음수든 양수든 절댓값이 큰 두 수끼리는 서로 곱하는 것이 유리하고, 1같은 경우는 그냥 더해주는 것이 유리하다.

코드 구현 - 자바

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

public class BJ_2036 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        // 1
        List<Long> positive = new ArrayList<>(); //양수
        List<Long> negative = new ArrayList<>(); //음수
        int ones = 0; //1의 갯수

        for (int i = 0; i < n; i++) {
            long num = Long.parseLong(br.readLine());

            if (num == 1) ones++;
            else if (num <= 0) negative.add(num);
            else positive.add(num);
        }

        Collections.sort(positive);
        Collections.sort(negative);

        // 2
        long ans = 0;

        //양수 계산, 큰 수부터
        for (int i = positive.size() - 1; i >= 0; i -= 2) {
            if (i - 1 >= 0) {
                ans += (positive.get(i) * positive.get(i - 1));
            } else {
                ans += positive.get(i); //홀수개 일 때, 마지막 하나 남은 수
            }
        }

        //음수 계산, 작은 수부터
        for (int i = 0; i < negative.size(); i += 2) {
            if (i + 1 < negative.size()) {
                ans += (negative.get(i) * negative.get(i + 1));
            } else {
                ans += negative.get(i); //홀수개 일 때, 마지막 하나 남은 수
            }
        }

        ans += ones; //1은 그냥 더함
        System.out.println(ans);
    }
}

1

• 입력 숫자를 양수와 음수, 1로 구분한다.
• 0까지 음수에 포함하는 이유는 만약 음수의 개수가 홀수개 일 때, 하나 남은 음수를 결과에 더하면 손해이다. 따라서 0과 곱하여 결과에 마이너스가 되지 않도록 하기 위함이다.
• 두 리스트를 정렬한다. 이는 최대한 큰 수를 만들기 위함이다.

2

• 양수는 큰 수부터, 음수는 작은 수부터(절댓값이 큰 수부터) 두개씩 곱하면서 결괏값에 더하는 작업을 한다.
• 두 리스트는 정렬되어 있기 때문에 최대한 절댓값이 큰 숫자끼리 곱해진다.
• 1은 어느 수와 곱해도 결국 자기 자신이다. 양수인 1을 낭비하기 보다는 그냥 더함으로써 최대한 결괏값을 크게 만들어준다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(NlogN)