[자바] 백준 1744 수 묶기

 

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

1744번: 수 묶기

 

하루 한 문제 풀기..(다시 1일차)

 

어제 안풀었습니다.

 

인생은 늘 계획처럼 흘러가지 않는 법이죠.

 

만약 어제가 막 98일차 였다면 굉장히 속상했겠지만, 어제는 2일차.. 무너져야한다면 지금 실패하는 것이 이득입니다. 

 

아무튼 문제 풀겠습니다. 

 

-문제 풀이

 

'1,000 부터 1,000인 수로 이루어진 수열에서 1)두 수를 뽑아 곱해서 더하거나, 2) 그냥 더해서 나올 수 있는 최대 값을 구하쇼' (N <= 50 , t<2sec)

 

문제 설명이 꼭 말은 많이 하는데, 별 쓸모가 없는 말만하는 저랑 비슷합니다. 

 

N이 50 이하, t <= 2sec 라서 브루트 포스 형식으로 풀어볼까 했는데, 50C2 * 48C2 * .... 의 경우의 수가 나와서 빠르게 포기하고 다른방법을 찾아봤습니다.

 

가장 큰 수가 나오게 하려면, 부호(음수, 양수)가 같은 절대값이 가장 큰 두 수를 곱해주는 조건이 대부분의 경우에서 적용이 될 것 같았습니다.

 

간만에 만나는 그리디 알고리즘입니다. 

 

여기서 잠깐

 

0이 가능하다는 점이 저를 곤란하게 만들었습니다. 양수랑 만나면 무적권 더해줘야 하고, 음수를 만나면 무적권 곱해줘야합니다. 이렇게 말하니까 되게 간단하네요.? 문제 풀때는 고민이였는데

 

아무튼 양수와 음수를 분리하여 내림차순 정렬을 통해 두 값씩 곱했습니다.  양수나 음수가 홀수여서 값이 남으면 마지막에 계산을 해줬습니다.

 

요즘 느끼는 건데 설명하는게 참 쉽지 않네요.

 

-코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;

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());
        PriorityQueue<Integer> maxQ = new PriorityQueue<>(Comparator.reverseOrder());
        PriorityQueue<Integer> minQ = new PriorityQueue<>();
        for(int i=0;i<n;i++){
            int nowInt = Integer.parseInt(br.readLine());
            if(nowInt>0){
                maxQ.add(nowInt);
            }else{
                minQ.add(nowInt);
            }
        }
        int answer = 0;
        int lastPlusValue =  1001,lastMinusValue=1001;
        while(!maxQ.isEmpty()){
            if(maxQ.size()==1) {
                lastPlusValue = maxQ.poll();
                break;
            }
            int a = maxQ.poll();
            int b = maxQ.poll();
            answer += Math.max(a+b,a*b);
        }
        while(!minQ.isEmpty()){
            if(minQ.size()==1) {
                lastMinusValue = minQ.poll();
                break;
            }
            int a = minQ.poll();
            int b = minQ.poll();
            answer += Math.max(a+b,a*b);
        }
        if(lastPlusValue!=1001 && lastMinusValue!=1001){
            answer+=Math.max(lastPlusValue+lastMinusValue,lastPlusValue*lastMinusValue);
        }else{
            if(lastPlusValue!=1001){
                answer+=lastPlusValue;
            }
            if(lastMinusValue!=1001){
                answer+=lastMinusValue;
            }
        }

        System.out.println(answer);

    }
}