우매함의 봉우리를 넘어서며 개발하면서 기록하기

백준 1744. 수 묶기

18 Apr 2021

문제 바로가기

수 묶기

문제 요약

image 길이가 N인 수열이 주어졌을 때 수열의 합을 구하는 문제. 이때, 숫자 2개를 묶어서 더할 수 있고 수열의 모든 수는 한번씩만 묶일 수 있고 묶이지 않을 수 있다. 수열의 수를 적절히 묶었을 때, 그 합이 최대가 되도록 만들어보자.

문제 풀이 포인트

굉장히 그리디스러운 문제다. 실제로 백준의 문제 분류도 그리디로 올라가있는데 합을 최대로 만들기 위해 생각해보아야할 포인트는

  1. 음수 * 음수는 양수가 된다.
  2. 크기가 큰 수끼리 곱할 수록 더 큰 수가 나온다.
  3. 단, 1의 경우 곱할때보다 더할때 더 큰 숫자가 나온다. 세가지 포인트로 문제를 해결했다.

해결 방법은

1. 숫자를 입력 받을 때 음수와 양수를 각각 나누어 리스트에 입력받는다. 
2. 음수의 경우 오름차순 정렬, 양수는 내림차순으로 정렬한다.
3. 리스트의 인덱스를 하나씩 찾아가면서 다음 인덱스가 존재한다면 서로 곱하고, 그렇지 않다면 그냥 합한다.

문제 코드[JAVA]

코드 펼치기 

import java.util.*;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    List<Integer> minus = new ArrayList<>();
    List<Integer> plus = new ArrayList<>();
    int N = sc.nextInt();
    for(int i = 0; i < N; i++) {
      int num = sc.nextInt();
      if(num <= 0) {
        minus.add(num);
      }
      else {
        plus.add(num);
      }
    }
    Collections.sort(minus); // 오름차순 정렬
    Collections.sort(plus, new Comparator<Integer>() { // 내림차순 정렬

      @Override
      public int compare(Integer o1, Integer o2) {
        return o2 - o1;
      }
    });
    int sum = 0;
    for(int i = 0; i < minus.size(); i++) {
      int num = minus.get(i);
      if(++i < minus.size()) {
        num *= minus.get(i);
      }
      sum += num;
    }
    for(int i = 0; i < plus.size(); i++) {
      int num = plus.get(i);
      if(++i < plus.size()) {
        if(plus.get(i) != 1) { 
          num *= plus.get(i);
        }
        else // 1이 여러개 연달아 나올때는 
             //곱하는것보다 더하는게 이득이므로 i를 줄여준다
          i--;
      }
      sum += num;
    }
    System.out.println(sum);
  }
}

Related posts