Java 백준 문제풀이 (58) 1744 _ 수 묶기

 

오늘은 수 묶기 문제다.

해당 유형의 문제는 모두 푸는 방법이 비슷하기 때문에, 하나만 혼자서 풀 수 있으면 나머지도 다 풀 수 있다.

우선 문제 조건을 정리하고 주석을 작성해보자.

 

 

        // 수열의 합, but 최대 2개의 수끼리 묶어 곱한 뒤 더할 수 있음
        // ex ) { 0, 1, 2, 3, 4, 5 } ?
        // => 0 + 1 + ( 2 * 3 ) + ( 4 * 5 ) == 최대값
 
        // 1. 큰 수끼리 곱하면 좋다.
        // 2. 0은 곱하면 안된다.
        // 3. 우선순위 큐를 쓰면 편하겠네요.
        // 4. 정답이 항상 2^31보다 작다고 한다.. long 쓰자..
        // 5. 문제는 음수다. 음수 양수를 따로 저장해야할 듯
        // 6. 음수의 경우 -> (절대값 기준)큰 수끼리 곱하면 좋다. 0이랑 곱해도 좋다.

 

수열에서 값을 두 개씩 묶거나 묶지 않은 상태로 곱한 뒤 더할 수 있다고 한다.

 

1. 큰 수끼리 곱했을 때 당연히 더 큰 값이 나온다.

2. 정수에 0을 곱하면 손해니까 곱하면 안된다.

3. 늘 그렇듯 우선순위 큐를 쓰는 게 가장 깔끔한 방법이다.

4. int의 범위가 2^31이라서 문제가 없을 것 같지만 찝찝하니까 난 long을 쓰겠다. 바꾸기 귀찮잖아요.

5. 근데 음수는 어떡하지? 음수는 오히려 작은 수끼리 곱하면 더 큰 값이 나오는데요.

6. 따라서 음수와 0은 별도의 우선순위큐에 넣는다.

 

=>

예를 들어 { 3, 2, 0, -2, -3, -4}인 경우

3과 2는 당연히 곱하는 게 좋다.

0은 더해도 아무 이득이 없고 곱하면 손해다, 얘는 음수랑 곱해서 음수 하나를 제거해버리는 것이 이득이다.

-3과 -4는 곱하면 12가 되므로 곱하면 좋다.

 

이제 위의 조건을 바탕으로 야매 수도코드를 작성해보자.

 

 

 

public class Main {
    public static void main(String[] args) throws Exception {
        // 수열의 합, but 최대 2개의 수끼리 묶어 곱한 뒤 더할 수 있음
        // ex ) { 0, 1, 2, 3, 4, 5 } ?
        // => 0 + 1 + ( 2 * 3 ) + ( 4 * 5 ) == 최대값
 
        // 1. 큰 수끼리 곱하면 좋다.
        // 2. 0은 곱하면 안된다.
        // 3. 우선순위 큐를 쓰면 편하겠네요.
        // 4. 정답이 항상 2^31보다 작다고 한다.. long 쓰자..
        // 5. 문제는 음수다. 음수 양수를 따로 저장해야할 듯
        // 6. 음수의 경우 -> (절대값 기준)큰 수끼리 곱하면 좋다. 0이랑 곱해도 좋다.
 
        // 수열 크기 N
 
        // 우선순위 큐 생성
        // 음수 우선순위 큐 생성
 
        // 반복문 ( i < N )
                // 우선순위 큐에 수열 입력 받기
                // 만약 0 혹은 음수라면
                // 음수 우선순위 큐에 수열 입력 받기
 
        // int answer = greedy(양수 큐, 음수 큐)
 
        // 정답 출력
 
    public static long greedy(Queue<Integer> positive, Queue<Integer> negative) {
        // 양수 결과 변수 p
        // 음수 결과 변수 n
 
        // while(positive.size > 0)
            // num1 = positive.poll()
            // 만약 다음 수가 없다면 p+=num1
                // 아니라면 p += (num1*num2)
 
        // while(negative.size > 0)
        // num1 = negative.poll()
        // 만약 다음 수가 없다면 n+=num1
        // 아니라면 n += (num1*num2)
        // 반환 p + n;
    }
}

 

 

맞았을까요 틀렸을까요.

나도 아직 안 풀어봐서 모른다.

 

근데 일단 주석만 봐도 마음에 안 드는 부분이, greedy 메서드에 중복 코드가 발생하고 있다.

불쾌하기 때문에 저 부분은 변경이 필요하다.

 

.

.

 

아니나 다를까 틀렸다.

큰 틀에서 잘못된 부분은 없으나 특정 경우의 수를 생각해보면 뭔가 잘못됐다는 사실을 알 수 있다.

숫자 하나만 생각하면 되는 거니까 직접 생각해보자.

정답은 아래에.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class Main {
    public static void main(String[] args) throws Exception {
        // 수열의 합, but 최대 2개의 수끼리 묶어 곱한 뒤 더할 수 있음
        // ex ) { 0, 1, 2, 3, 4, 5 } ?
        // => 0 + 1 + ( 2 * 3 ) + ( 4 * 5 ) == 최대값
 
        // 1. 큰 수끼리 곱하면 좋다.
        // 2. 0은 곱하면 안된다.
        // 3. 우선순위 큐를 쓰면 편하겠네요.
        // 4. 정답이 항상 2^31보다 작다고 한다.. long 쓰자..
        // 5. 문제는 음수다. 음수 양수를 따로 저장해야할 듯
        // 6. 음수의 경우 -> (절대값 기준)큰 수끼리 곱하면 좋다. 0이랑 곱해도 좋다.
 
        // 수열 크기 N
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
 
        // 우선순위 큐 생성
        Queue<Integer> positive = new PriorityQueue<>((n1, n2) -> n2 - n1);
        // 음수 우선순위 큐 생성 (기준 변경 필요)
        Queue<Integer> negative = new PriorityQueue<>((n1, n2) -> n1 - n2);
 
        int answer = 0;
 
        // 반복문 ( i < N )
        for (int i = 0; i < N; i++) {
            int n = Integer.parseInt(br.readLine());
            if (n == 1) {
                answer += n;
            }
            else if (n > 0) {
                // 우선순위 큐에 수열 입력 받기
                positive.add(n);
            } else {
                // 만약 0 혹은 음수라면
                // 음수 우선순위 큐에 수열 입력 받기
                negative.add(n);
            }
        }
 
        // int answer = greedy(양수 큐, 음수 큐)
        long positiveResult = getSum(positive);
        long negativeResult = getSum(negative);
        answer += (positiveResult + negativeResult);
 
        // 정답 출력
        System.out.println(answer);
    }
 
    public static long getSum(Queue<Integer> queue) {
        // 양수 결과 변수 p
        // 음수 결과 변수 n
        long p = 0;
 
        // while(positive.size > 0)
        while (queue.size() > 0) {
            // num1 = positive.poll()
            int num1 = queue.poll();
            // 만약 다음 수가 없다면 p+=num1
            if (queue.isEmpty()) {
                p += num1;
            } else {
                // 아니라면 p += (num1*num2)
                int num2 = queue.poll();
                p += (num1 * num2);
            }
        }
        // while(negative.size > 0)
        // num1 = negative.poll()
        // 만약 다음 수가 없다면 n+=num1
        // 아니라면 n += (num1*num2)
        // 반환 p + n;
 
        return p;
    }
}

늘 그렇듯 주석은 무시하자.