[JAVA] 백준 1744 그리디

 

 

 

1744번: 수 묶기

문제

수를 묶거나(두 수의 곱) 묶지않고 주어진 수열의 합의 최댓값을 구하여라.

풀이

3가지의 경우의 수로 나눠서 최선이 무엇인지 생각해보고 풀었습니다.

1. 양수의 경우는 큰 값끼리 묶는 것(곱하는 것)이 가장 최선
2. 음수의 경우는 가장 작은 값끼리 묶는 것(곱하는 것)이 가장 최선
3. 음수 중에서 남는 값이 있다면 묶는 것(곱하는 것)이 가장 최선

양수의 경우

             while (positive.size() > 1 ){
           int x = positive.poll();
           int y = positive.poll();
           if(x + y > x * y) answer += x + y;
           else answer += x * y;
        }
                if(!positive.isEmpty()) answer += positive.poll();

x + y가 x * y보다 큰 경우 x + y 선택 → 두 값중 하나가 1이라면 덧셈이 더 크다.

큐에 남은 값을 더한다.

음수의 경우

                 while (negative.size() > 1){
           answer += negative.poll()*negative.poll();
       }

가장 작은 값을 곱해 answer에 더해준다.

0의 경우

if(!negative.isEmpty()) answer += zero > 0 ? 0 : negative.poll();

음수 큐에 값이 남아있고 0값이 있으면 0을 더한다.

아니라면 남은 음수 값을 더한다.

전체 코드

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

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

       int N = Integer.parseInt(br.readLine());

        // 양수는 양수끼리 큰 값을 곱하는게 최선
        PriorityQueue<Integer> positive = new PriorityQueue<>((o1, o2) -> {
           return o2 - o1;
        });

        // 음수는 음수끼리 작은 값을 곱하는게 최선
        PriorityQueue<Integer> negative = new PriorityQueue<>();

        // 0은 그냥 더하거나 짝이 없는 음수값과 곱하는게 최선
        int zero = 0;

       for(int i=0; i<N; i++){
           int value = Integer.parseInt(br.readLine());
           if(value > 0) positive.add(value);
           else if(value < 0) negative.add(value);
           else zero++;
       }

       int answer = 0;
       while (positive.size() > 1 ){
           int x = positive.poll();
           int y = positive.poll();
           if(x + y > x * y) answer += x + y;
           else answer += x * y;
       }
       if(!positive.isEmpty()) answer += positive.poll();

       while (negative.size() > 1){
           answer += negative.poll()*negative.poll();
       }
       if(!negative.isEmpty()) answer += zero > 0 ? 0 : negative.poll();

        System.out.println(answer);

    }
}

결과