[BOJ] 1744 수 묶기 - JAVA

1. 문제

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이 되어 최대가 된다.

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

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

---

2. 풀이

1.  양수, 음수, 0, 1을 구분했다. 0은 존재하는지만 체크하고 1은 갯수를 센다. 그 외의 숫자는 양수, 음수 각 리스트에 더한다. 

2.  양수는 내림차순, 음수는 오름차순으로 정렬한 뒤 두개씩 곱해 answer에 더한다.

3.  만약 양수의 개수가 짝수가 아니라면 나머지 하나(가장 작은 양수)를 answer에 그대로 더한다.

4.  만약 음수의 개수가 홀수가 아니고 0이 없다면 절댓값이 가장 작은 음수를 answer에 그대로 더한다.

5.  answer에 1의 개수를 더해 출력한다. (1은 곱하면 오히려 손해가 나는 수이기 때문에 따로 더한다.)

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

public class BOJ_1744_수묶기 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());
      ArrayList<Integer> plus = new ArrayList<>();
      ArrayList<Integer> minus = new ArrayList<>();
      int num;
      boolean zero = false;
      int one = 0;
      for(int i=0;i<N;i++){
         num = Integer.parseInt(in.readLine());
         if(num<0) minus.add(num);
         else if(num==0) zero = true;
         else if(num==1) one++;
         else plus.add(num);
      }

      Collections.sort(plus,(o1,o2)->o2-o1);
      Collections.sort(minus);

      int answer = 0;
      int psize = plus.size();
      int msize = minus.size();
      for(int i=0;i+1<psize;i+=2){
         answer += plus.get(i)*plus.get(i+1);
      }
      for(int i=0;i+1<msize;i+=2){
         answer += minus.get(i)*minus.get(i+1);
      }
      if(psize%2!=0) answer += plus.get(psize-1);
      if(msize%2!=0 && !zero) answer += minus.get(msize-1);


      System.out.println(answer+one);

   }

}

 

---

3. 결과

양수, 음수를 구분하지 않고 한 리스트에 모은 뒤 0개수, 1개수, 양수개수, 음수개수를 저장해둔 뒤 오름차순으로 정렬해서 사용해도 된다.

음수개수가 홀수일 때 개수-1까지 answer에 두개씩 곱해 더하고, 양수가 홀수개일때 음수+0개수+1개수+1부터 answer에 두개씩 곱해 더하면 된다.

위에 해당하지 않는 수들은 answer에 그대로 더하면 된다.