[백준 1744][Gold 4] - 수 묶기(JAVA)

 

문제 링크

---

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

 

문제

---

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.

예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다.

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 수열의 크기 N이 주어진다. N은 50보다 작은 자연수이다. 둘째 줄부터 N개의 줄에 수열의 각 수가 주어진다. 수열의 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

 

출력

---

수를 합이 최대가 나오게 묶었을 때 합을 출력한다. 정답은 항상 2^31보다 작다.

 

문제 해석

---

문제의 조건을 나열하면 다음과 같다.

• 주어질 수의 개수은 50이하이다
• 수는 -1,000이상 1,000이하이다.
• 모든 수는 합하거나 곱할 수 있다.
  • 만약 곱셈(수를 묶는다.)를 진행한 경우 연속으로 한번 밖에 하지 못한다.

 

문제 접근

---

가장 큰수를 만들기 위해선 곱샘을 많이 사용하면 된다. 하지만 수는 단 한번만 묶일 수 있기 때문에 연속으로 곱샘을 하지 못한다. 그러므로 가장 많이 곱샘을 사용하는 방법은 아래와 같다.

 

(10 * 10) + (11 * 10) + (10 * 9) + ... + (2 * 2)

 

이렇게 2개씩 짝을 지어서 곱해주고 모든 값을 더하면 최대한 많이 곱셈을 사용하므로 가장 큰 값을 얻을 수 있을 것이다.

 

음수 VS 양수

---

이 문제는 음수와 양수가 동시에 존재한다. 그러므로 각각의 경우를 따로 생각해야 하므로 음수와 양수를 각자 분리해서 저장한 뒤 짝을 지은다. 이때 곱셈을 진행하는 경우 음수는 가장 작은 수 끼리, 양수는 가장 큰 수 끼리 짝을 지어야 가장 큰 연산 값을 얻을 수 있다!

 

10 * 1 < 10 * 9
-1 * -2 < -100 * -101

 

그러므로 음수는 오름차순, 양수는 내림차순으로 정렬해 짝을 만들어 주면 가장 큰 값이 나오는 짝을 만들 수 있다.

 

1. 음수

음수는 덧셈을 하면 무조건 음수지만 곱셈을 하면 무조건 양수가 된다. 그러므로 음수의 짝은 곱셈만 진행하여 큰 수를 만든다.

남는 짝이 있다면 음수의 경우 더해주면 무조건 작아진다. 하지만 0이 있다면 0과 음수를 곱해주면 0이 되기 때문에 남은 음수를 그대로 더하는 것 보다 커지게 된다. 그러므로 0이 있는 경우에는 0과 짝을지어 곱해주고 아니라면 음수를 그냥 더하는 것이 가장 큰 수를 만드는 방법이다.

 

2. 양수

양수도 웬만하면 곱셈이 덧셈보다 커지지만 짝을 지은 숫자 중 하나가 1인 경우 곱셈보다 덧셈이 큰 경우가 있다.

1 + 5 = 6          >        1 * 5 = 5 

 

그러므로 곱셈과 덧셈을 한 뒤 큰 값을 더하면 가장 큰 수를 구할 수 있을 것이다.

 

 

 

남는 양수가 있다면 양수의 경우 더해주면 무조건 커진다. 그러므로 남은 양수는 덧셈을 진행한다.

 

 

 

사용 알고리즘 : 그리디( O(n) = nlogn )

---

가장 큰 값을 찾는 방법은 그리디, 완전 탐색, DP 등이 있는데 완전 탐색을 사용하는 경우 50개의 숫자로 조합을 만드는데 최대 50!이 든다. 그러므로 1초 이내의 시간안에 가능하지 않다고 판단했다.

가장 빠른 방법은 그리디이기 때문에 그리디로 생각해봤는데 위의 방법으로 가장 큰 수끼리 묶어서 당장의 큰 수를 만들고 모두 더하면 가장 큰 수를 만들 수 있었다. 위의 방법의 경우 양수, 음수를 나누고 가장 큰 수 끼리 묶기 위해 정렬이 필요하므로 정렬의 시간 복잡도인 nlogn의 시간이 든다. 그리고 모든 숫자를 딱 한번만 탐색하기 때문에 O(n)의 시간복잡도가 추가로 든다. 그러므로 최종적인 시간 복잡도는 아래와 같다.

 

O(n) = (정렬 시간) + (양수,음수 탐색시간)
= nlogn + n
≒ nlogn

 

nlogn이고 n = 50이기 때문에 1초의 시간 이내로 해결할 수 있다!

 

코드

---

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));
        int N = Integer.parseInt(br.readLine());

        //음수는 오름차순, 양수는 내림차순으로 정렬해 가장 큰 수끼리 짝을 지을 수 있도록 한다.
        PriorityQueue<Integer> negativePQ = new PriorityQueue<>();  //음수
        PriorityQueue<Integer> positivePQ = new PriorityQueue<>(Collections.reverseOrder());    //양수

        int zeroCount = 0;  //0이 나온 홧수

        //입력되는 수 저장
        for(int i=0;i<N;i++){
            int num = Integer.parseInt(br.readLine());

            if(num ==0){
                zeroCount++;
            }else if(num < 0){
                negativePQ.add(num);
            }else{
                positivePQ.add(num);
            }
        }

        int sum = 0;    //가장 큰 수

        //음수의 수를 짝을 지어 곱셈수를 저장
        while(negativePQ.size() > 1){
            int a = negativePQ.poll();
            int b = negativePQ.poll();
            sum += a*b; //음수는 곱셈을 하면 양수가 되므로 곱셈이 무조건 커진다.
        }

        //짝이 남은 수가 있는 경우
        if(!negativePQ.isEmpty()){
            int num = negativePQ.poll();

            //0이 있다면 0과 곱하면 음수가 없어져 더 큰수가 된다.
            //하지만 0이 없다면 남은 수는 더하는 방법밖에 없다.
            if(zeroCount == 0){
                sum += num;
            }
        }

        //양수의 수를 짝을 지어 곱셈수를 저장
        while(positivePQ.size() > 1){
            int a = positivePQ.poll();
            int b = positivePQ.poll();

            sum += Math.max(a * b, a + b);  //곱셈과 덧셈 중 큰 수를 저장한다.
        }
        
        //남은 수가 있다면 더해준다.
        if(!positivePQ.isEmpty()){
            sum += positivePQ.poll();
        }

        System.out.println(sum);
    }
}

 

 

실행 결과

---

제출 결과

1초안에 문제가 해결 되었다!

 

키워드

---

• 가장 큰 숫자
  
  • 가장 큰~ 이란 말이 붙으면 완전탐색, 그리디 , DP의 가능성을 가지고 있다

 

팁

---

1. N이 50의 모든 조합의 경우는 2^50 이므로 완전탐색이 아닌 경우가 높으므로 다른 방법을 생각한다.
2. 1, 0, -1인 경우는 사칙연산을 할 때 변수를 일으키므로 유의한다.