[자바] 백준 2036 - 수열의 점수 (java)

목차

문제 : boj2036

 

 

필요 알고리즘

• 그리디
  
  • 최선의 방법을 찾아 규칙대로 구현하면 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  입력으로 들어오는 값은 결국 음수, 0, 양수 이렇게 3가지 종류이다.

이 때 곱해서 이득이 되는걸 생각해보자. 음수와 음수, 음수와 0, 양수와 양수 이렇게 3가지 경우이다. 그 외의 경우엔 항상 손해이다. 또한 음수와 0 보다는 음수와 음수가 더 이득이다.

 

  그래서 대충 아래와 같이 생각했고, 구현했더니 통과되었다. 주의점은 답은 당연히 int의 범위를 넘으므로 long에 더해줘야 한다. 그리고 두 수를 곱할 때에도 int의 범위를 넘을 수 있으므로 long으로 처리해줘야 한다.

 

1. 음수와 양수를 분리해서 따로 리스트에 저장 후 각각 정렬한다. 이 때 0은 1개라도 존재했는지만 기록해둔다.

while (n-->0) {
    Integer cur = Integer.parseInt(br.readLine());
    if (cur == 0) zeroCnt++;
    else if (cur < 0) negative.add(-cur);
    else positive.add(cur);
}

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

 

2. 음수에서 절대값이 큰 값부터 2개씩 뽑아서 곱해 답에 더해준다. 음수의 갯수가 홀수이면 절대값이 가장 낮은 음수가 하나 남는다. 이 때 0이 1개라도 있었다면 0과 곱해준다. 0이 없었다면 어쩔수없이 정답에서 빼줘야한다.

for (int i = 1; i < negative.size(); i+=2) {
    sum += 1l * negative.get(i) * negative.get(i-1);
}
if (negative.size()%2 == 1 && zeroCnt == 0) sum -= negative.get(negative.size()-1);

 

3. 양수의 경우 큰 수는 곱해주는게 이득이지만, 1과 2 혹은 1과 1 처럼 곱하면 오히려 손해인 경우도 있다. 따라서 큰 수부터 2개씩 뽑아서 곱해주는건 동일하지만, 곱한 것과 더한 것 중 이득인걸 답에 더한다. 마찬가지로 홀수라면 가장 작은 양수가 하나 남는데 이건 그냥 답에 더해주면 된다.

for (int i = 1; i < positive.size(); i+=2) {
    int a = positive.get(i);
    int b = positive.get(i-1);
    sum += Math.max(a+b, 1l*a*b);
}
if (positive.size()%2 == 1) sum += positive.get(positive.size()-1);

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        List<Integer> negative = new ArrayList<>();
        List<Integer> positive = new ArrayList<>();
        int zeroCnt = 0;

        while (n-->0) {
            Integer cur = Integer.parseInt(br.readLine());
            if (cur == 0) zeroCnt++;
            else if (cur < 0) negative.add(-cur);
            else positive.add(cur);
        }

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

        long sum = 0;
        for (int i = 1; i < negative.size(); i+=2) {
            sum += 1l * negative.get(i) * negative.get(i-1);
        }
        if (negative.size()%2 == 1 && zeroCnt == 0) sum -= negative.get(negative.size()-1);

        for (int i = 1; i < positive.size(); i+=2) {
            int a = positive.get(i);
            int b = positive.get(i-1);
            sum += Math.max(a+b, 1l*a*b);
        }
        if (positive.size()%2 == 1) sum += positive.get(positive.size()-1);

        System.out.println(sum);
    }
}