[백준] 알고리즘 분류(그리디 알고리즘,JAVA)1744번, 수 묶기

문제 링크

1744번: 수 묶기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 묶는 수는 두 개의 수를 곱한 값입니다.

2. 묶는 수는 한 번만 적용이 가능합니다.

3. -1000 ≤ N개의 수 ≤ 1000의 범위를 가집니다.

4. 묶는 수를 이용하여 N개의 합의 최대값을 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 묶는 수를 최대한 이용한 최대합을 구해서 결과로 출력합니다.

 

 

묶는 수.

 

양수 일 때에는 내림차순, 음수 일 때에는 오름차순으로 정렬되는 PriorityQueue를 이용하여 정렬되도록 하였습니다.

 

양수 일 때

 

묶는 수를 해서 최대값을 구하려면 : 큰 값 × 큰 값

 

값이 1일 때에는 더하기.

 

1 2 3 4일 때

1 + 2 + (3 × 4) = 15가 최대값

(3 × 4) : 큰 값 × 큰 값

1 + 2 : 값이 1인 것은 더했기 때문에 남은 가2는 곱할 값이 없으므로 더하기.

 

음수 일 때

 

묶는 수를 해서 최대값을 구하려면 : 작은 값 × 작은 값

 

값이 0일 때에는 항상 곱하기.

 

-3 -2 -1 0일 때

(-3 × -2) + (-1 × 0) = 6이 최대값

(-3 × -2) : 작은 값 × 작은 값

(-1 × 0) : 값이 0일 때에는 항상 곱하기

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 4

 

-1

 

2

 

1

 

3

 

2. 묶는 수를 최대한 이용한 최대합을 구해서 결과로 출력합니다.

 

음수

 

-1

 

최대값 : -1

 

양수

 

3

2

1

최대값 : (3 × 2) + 1 = 7

(3 × 2) : 큰 값 × 큰 값

+ 1 : 값이 1이기 때문에 더하기

 

최대값 : 6

 

양수 + 음수 = 7 + (-1) = 6

 

6을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• PriorityQueue를 양수와 음수를 저장하고 양수는 내림차순, 음수는 오름차순으로 저장되도록 하였습니다.
• 음수일 때와 양수일 때에 최대값을 구합니다.
• 음수와 양수의 최대값을 더한 값을 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

import java.io.*;
import java.util.*;


public class Main {
    static int N;
    //양수 관련 값 저장, 내림차순 정렬
    static PriorityQueue<Integer> plus = new PriorityQueue<>(Comparator.reverseOrder());
    //음수 관련 값 저장, 오름차순 정렬
    static PriorityQueue<Integer> minus = new PriorityQueue<>();
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        //N개의 입력값 양수와 음수로 나뉘어 저장
        for(int i=0;i<N;i++){
            int num = Integer.parseInt(br.readLine());
            if(num <= 0)
                minus.add(num);
            else
                plus.add(num);
        }
        int answer = 0;
        //음수일 때 최대값 구하기
        while(!minus.isEmpty()){
            int cur = minus.poll();
            if(minus.isEmpty()){	//마지막 하나 남은 값일 때 더하기
                answer += cur;
                break;
            }
            //다음 남은 값이 0일 때
            if(minus.peek() == 0)
                minus.poll();
            //작은 값 × 작은 값
            else
                answer += cur * minus.poll();
        }
        //양수일 때 최대값 구하기
        while(!plus.isEmpty()){
            int cur = plus.poll();
            //마지막 하나 남은 값일 때 더하기
            if(plus.isEmpty()){
                answer += cur;
                break;
            }
            //값이 1일 때 더하기.
            if(cur == 1)
                answer += 1;
            //다음 묶을 쌍이 1일 때에도 더하기
            else if(plus.peek() == 1)
                answer += cur + plus.poll();
            //큰 값 × 큰 값
            else
                answer += cur * plus.poll();
        }
        bw.write(answer + "");	//최대합 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}