[Java] BOJ(백준) 2036 수열의 점수

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

2036번: 수열의 점수

 

그리디 문제다.

주어진 수열에서 최대 합을 구하는 문제다.

합을 할 수 있는 방법은 1. 한 개의 수 더하기 2. 두 수의 곱 더하기

정렬을 해서 양수와 음수를 따로 계산하는 방법을 떠올렸다.

이와 비슷한 문제를 푼 적이 있는데 https://www.acmicpc.net/problem/1461 이 문제다.

 

수열을 입력 받으면서 음수의 개수를 세어두고, 수열을 정렬한다.

주의해야 할 점은

1. 큰 값 끼리 곱한 것이 제일 크다.

2. 음수와 음수의 곱은 양수다.

3. 0과 음수를 곱하면 0이 되므로 음수를 카운트 할 때 0도 포함한다.

4. 1과 다른 수를 곱하는 것 보다 1은 한 개 더해주는 것이 합이 커진다.

5. 큰 값 끼리 곱해야 하므로 배열의 양 끝에서부터 두 개 씩 곱하면서 0과 가까운 수로 가야한다.

 

정말 주의해야 할 점은 int 범위 내에서 해결할 수 없다는 점이다.

 

최근에 자바로 문제를 풀어보고 있는데 int로 해결이 안된다는 것을 깨닫고 자료형을 다 long으로 바꿨다.

그런데 계속 틀렸습니다가 떠서 알고보니 입력받아 오는 과정에서 Integer.parseInt(); 부분을 바꾸지 않았다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int n;
    static int one;
    static int minus;
    static long res;
    static long[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());

        arr = new long[n];

        for (int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            arr[i] = Long.parseLong(st.nextToken());

            if (arr[i] <= 0){
                minus++;
            }else if (arr[i] == 1){
                one++;
            }
        }

        Arrays.sort(arr);

        for (int i = 0; i < minus; i += 2){
            if (i + 1 < minus){
                res += arr[i] * arr[i + 1];
            }else {
                res += arr[i];
            }
        }

        for (int i = n - 1; i >= minus + one; i-= 2){
            if (i - 1 >= minus + one){
                res += arr[i] * arr[i - 1];
            }
            else {
                res += arr[i];
            }
        }

        System.out.println(res + one);
    }
}