백준 2036번: 수열의 점수 (Python/Java)

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

2036번: 수열의 점수

 

 

 

접근

---

그리디 알고리즘의 기본 원리만 생각하며 원론적으로 접근해봤다. '배열에서 가장 큰 숫자를 만들어 더하는 것'이 현재 단계에서 해야 하는 최선의 선택이다. 이 부분을 구현하기 위해 우선 두 가지 경우로 나눠서 생각해봤다.

 

첫 번째는 홀수인 경우다. 홀수인 경우는 무조건 두 개를 곱해야 최종 값이 가장 큰 값이 나온다. 홀수 숫자의 개수가 홀수개인 경우에는 두 개씩 곱하다가 마지막 홀수를 더해야 한다. 홀수와 짝수를 곱하면 괜히 짝수를 더해 더 높은 값을 낼 수 있는 기회를 날리게 된다. 예를 들어 다른 홀수는 이미 처리하고 마지막 -1이 남았다. 짝수 1과 곱하면 최종 값에 -1을 더하게 된다. 하지만 둘을 곱하지 않고 각각 더하면 -1과 1이 더해지고 최종적으로 0을 더하게 되니 최소한 최종 값이 줄지는 않는다.

 

두 번째는 짝수인 경우다. 짝수의 경우에도 홀수 경우와 같이 무조건 곱하고, 전체 개수가 홀수개라 마지막 남은 숫자 하나는 더하면 된다. 하지만 홀수 경우와 다르게 한 가지 조건이 또 붙는다. 숫자 1의 경우에는 무조건 더한다. 이 또한 예를 들어 생각해보자. 1과 2를 곱하면 2가 된다. 최종 값에는 2가 더해진다. 하지만 1과 2를 각각 더하면 최종 값에 3이 더해진다.

 

덧붙여 0인 경우는 홀수 경우에 넣어서 생각했다. 짝수의 경우에는 0을 곱하면 0이 되어 최종 값이 늘지 않고 더해봤자 0을 더하는 것이니 영향을 미치지 않지만, 홀수에 넣어서 곱하면 줄어들 값이 0이 되어 최종 값이 줄어드는 것을 막을 수 있기 때문이다.

 

예제를 통해 살펴보자. [-1, 5, -3, 5, 1]을 나눠서 정렬해보면 홀수는 [-3, -1], 짝수는 [5, 5, 1]이 된다.(계산의 편의를 위해 짝수는 거꾸로 정렬했다) 홀수 두 개는 곱하면 3, 짝수 배열 앞의 두 숫자를 곱하면 25, 마지막 숫자 1이 되고 이 셋을 더하면 29가 나온다. 

 

[-1, 5, -3, -1, 0, 1, 2, 1, 5]의 경우를 생각해보자 홀수는 [-3, -1, -1, 0], 짝수는 [5, 2, 1, 1]가 된다. 앞서 설명했듯 0은 홀수 배열에 넣어줬다. 홀수를 두 개씩 짝지어 더하면 3과 0이 된다. 이제 0을 홀수에 넣은 이유가 감이 잡일 것이다. 짝수 배열을 살펴보자. 앞의 두 숫자를 곱하면 10이다. 뒤의 두 1은 곱하면 1을 더하게 되지만 각각 더하면 2를 더할 수 있게 된다. 이렇게 3과 10과 2를 더해 15라는 값을 만들 수 있다.

 

 

 

풀이

---

Python

listNum = int(input())

leftBoard = []
rightBoard = []
for i in range(listNum):
  testNum = int(input())
  if testNum <= 0:
    leftBoard.append(testNum)
  else:
    rightBoard.append(testNum)

leftBoard = sorted(leftBoard)
rightBoard = sorted(rightBoard, reverse=True)

result = 0
for i in range(0, len(leftBoard), 2):
  if i < (len(leftBoard)-1):
    result += (leftBoard[i]*leftBoard[i+1])
  else:
    result += leftBoard[i]

for i in range(0, len(rightBoard), 2):
  if i < (len(rightBoard)-1):
    if rightBoard[i] == 1 or rightBoard[i+1] == 1:
      result += (rightBoard[i]+rightBoard[i+1])
    else:
      result += (rightBoard[i]*rightBoard[i+1])
  else:
    result += rightBoard[i]

print(result)

 

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {

    Scanner scan = new Scanner(System.in);

    int listNum = Integer.parseInt(scan.nextLine());

    ArrayList<Integer> leftBoard = new ArrayList<>();
    ArrayList<Integer> rightBoard = new ArrayList<>();
    for (int i = 0; i < listNum; i++) {
      int testNum = Integer.parseInt(scan.nextLine());

      if (testNum <= 0) {
        leftBoard.add(testNum);
      } else {
        rightBoard.add(testNum);
      }
    }

    Collections.sort(leftBoard);
    Collections.sort(rightBoard, Collections.reverseOrder());

    long result = 0;
    for (int i = 0; i < leftBoard.size(); i += 2) {
      if (i < (leftBoard.size() - 1)) {
        result += ((long) leftBoard.get(i) * (long) leftBoard.get(i + 1));

      } else {
        result += (leftBoard.get(i));
      }
    }

    for (int i = 0; i < rightBoard.size(); i += 2) {
      if (i < (rightBoard.size() - 1)) {
        if (rightBoard.get(i) == 1 || rightBoard.get(i + 1) == 1) {
          result += (rightBoard.get(i) + rightBoard.get(i + 1));
        } else {
          result += ((long) rightBoard.get(i) * (long) rightBoard.get(i + 1));
        }

      } else {
        result += rightBoard.get(i);
      }
    }

    System.out.println(result);

  }

}

 

 

 

후기

---

회사 일이 바빠 알고리즘에 신경 쓸 시간이 없어 안 그래도 빈약했던 그리디 알고리즘 문제를 조금 소홀히 했더니 아이디어를 생각해내는 머리가 조금 굳은 것 같은 느낌이다. 오늘 푼 문제도 일부러 낮은 난이도의 문제를 골라서 풀었다. 당분간은 너비 우선 탐색 외에 평소 소홀했던 알고리즘에 조금 더 집중하도록 해야겠다