알고리즘 풀이 - 백준 1744(수 묶기, 그리디(Greedy))

 

관련글

 

그리디 알고리즘 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

길이가 N인 수열이 주어질 때, 수열의 두 수를 묶는 경우 곱셈을 하고 나머지는 덧셈을 할 때, 각 수는 두개씩 묶이거나 묶이지 않을 수 있다면 그 합이 최대가 되는 결과를 구하는 문제

 

 

2. 풀이

 

2개의 숫자를 곱하는 경우가 가능할 때, 숫자가 가장 커지는 합을 구하는 방법은 다음의 규칙을 따른다.

 

① 0 또는 음수는 가장 작은 수 2개를 곱해서 양수로 만들면 제일 큰 경우가 된다.
② 1은 다른 수와 곱하면 1을 낭비하게 되므로 그냥 덧셈 처리한다.
③ 1보다 큰 양수는 가장 큰 수 2개를 곱하면 제일 큰 경우가 된다.

 

위의 규칙을 활용하여 수를 입력 받을 때, 음수 또는 0을 저장하는 저장소와 1보다 큰 양수를 저장하는 저장소를 별도로 만들어서 저장하면 된다.

1이 만약 숫자에 포함되어 있는 경우는 바로 정답에 그냥 더해 준다.

 

0 또는 음수가 저장된 저장손는 최소값부터 2개씩 꺼내서 곱하기 위해 오름차순으로 정렬하고 1보다 큰 양수를 저장하는 저장소는 내림차순 정렬한다.

이후, 저장소에 저장된 자료가 없을 때까지 곱셈 및 덧셈을 수행하여 전체 정답을 구하면 된다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

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

public class Main{
    static int n;
    public static void main(String[] args) throws IOException{
    
        // 주어진 n과 각 n개의 숫자를 양수, 음수, 1로 구분하여 저장한다.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        
        // 양수를 저장하는 우선순위 큐. 큰 수 부터 우선하여 저장한다.
        PriorityQueue<Integer> positive = new PriorityQueue<>(Collections.reverseOrder());
        
        // 음수 또는 0을 저장하는 우선순위 큐. 작은 수 부터 우선하여 저장한다.
        PriorityQueue<Integer> negative_zero = new PriorityQueue<>(); // 음수, 0을 저장
        
        // 정답이 저장된 변수
        long ans = 0;
        for(int i=0; i < n; i++){
            int num = Integer.parseInt(br.readLine());
            
            // 음수 또는 0인경우 negative_zero 우선순위 큐에 저장
            if(num <= 0){
                negative_zero.offer(num);
                
            // 1인 경우는 별도로 넣지 않고 덧셈
            } else if(num == 1){
                ans += 1;
                
            // 1보다 큰 양수이면 positive 우선순위 큐에 저장
            } else {
                positive.offer(num);
            }
        }
        
        // 두 우선순위 큐가 모두 빈 상태가 아니라면 지속 수행
        while(!negative_zero.isEmpty() || !positive.isEmpty()){
        
            // 음수 혹은 0이 든 우선순위 큐의 크기가 2 이상이면 2개를 빼서 곱하고 더한다.
            if(negative_zero.size() >= 2){
                ans += (negative_zero.poll() * negative_zero.poll());
                
            // 크기가 1이하면 빌 때까지 값을 빼서 더한다.
            } else {
                while(!negative_zero.isEmpty()) {
                    ans += negative_zero.poll();
                }
            }
            
            // 양수가 든 우선순위 큐의 크기가 2 이상이면 2개를 빼서 곱하고 더한다.
            if(positive.size() >= 2){
                ans += (positive.poll() * positive.poll());
            
            // 크기가 1이하면 빌 때까지 값을 빼서 더한다.
            } else {
                if(!positive.isEmpty()) {
                    ans += positive.poll();
                }
            }
        }
        
        System.out.println(ans);
        br.close();
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.