[백준] 1744번 파이썬 - 그리디

문제요약 (1744. 수 묶기)

주어진 수열을 적절히 묶거나 더해서 그 합이 최대가 되도록 한다. 이때 수열의 모든 수는 한 번만 묶거나 묶지 않아야 한다.

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

수열에 음수인 수가 있을 때 처리를 중심으로 생각하는 것이 중요하다. 그리고 생각지도 못한 숫자가 하나 있을 수 있으니 주의하자.

1744번: 수 묶기

 

풀이를 위한 부연 설명

• 다양한 케이스 별로 나눠서 문제를 풀어야한다.
  • 필자의 경우 직접 예제 수열을 만들면서 케이스를 나눠갔다.
• 오름차순으로 정리하는 것이 필수적이다.
  • 시간 복잡도를 고려하여 PriorityQueue를 반드시 사용해야한다.
• 먼저 음수의 처리가 중요하다고 생각하여 {-5, -4, -3, -2, -1} 수열을 가정하고 케이스를 나눴다
  • 수열 내의 음수가 짝수라면 2개씩 짝지어서 곱하도록 하고 더해주면 된다. (음수 X 음수 = 양수)
  • 수열 내의 음수가 홀수라면 2개씩 짝지어서 곱한 뒤, 마지막 하나만 따로 처리해주면된다. 
    • 만약 0이 수열 내에 존재한다면 음수와 곱해서 0으로 만든 뒤 더해도 된다.
    • 0이 없다면 그냥 합에 남은 음수를 더한다.
• 양수도 마찬가지로 짝수개인지 확인해본다.
  • 수열 내의 음수가 짝수라면 2개씩 짝지어서 곱하도록 하고 더해주면 된다.
  • 수열 내의 음수가 홀수라면 2개씩 짝지어서 곱하면 되지만, 맨 처음 수(양수 중 가장 작은 수)는 그냥 더한다.
  • 이때 주의할 점!!! 1은 곱하지 않고 더해야한다.
    • ex. {1, 1, 1, 1} 인 경우 단순히 2개씩 묶어서 더하면 2가 나오지만 전부 더하면 4가 된다
• 이러한 로직을 바탕으로 입력을 받을 때, 음수(-)/ 영(0) / 일(1) / 양수(+) 로 나눠서 계산한다.
• 그리디 에 대한 자세한 개념 설명과 연관 문제는 다음 링크를 참고하면 된다.

[코테 알고리즘] DFS, BFS / 관련 문제

 

코드 

import sys
input = sys.stdin.readline
from queue import PriorityQueue

n = int(input().rstrip())

nums = PriorityQueue()
minus = 0
zero = 0
one = 0
plus = 0
sumMul = 0

for _ in range(n):
    new = int(input().rstrip())
    if new < 0:
        minus += 1
    elif new == 0:
        zero += 1
    elif new == 1:
        one += 1
    else:
        plus += 1
    nums.put(new)

# minus
if minus > 0:
    div = minus // 2

    for _ in range(div):
        num1 = nums.get()
        num2 = nums.get()
        sumMul += num1*num2

# zero
if zero > 0:
    if minus % 2 == 1:
        zero += 1
    for _ in range(zero):
        nums.get()
else:
    if minus % 2 == 1:
        sumMul += nums.get()

# one
if one > 0:
    for _ in range(one):
        sumMul += nums.get()

# plus
if plus > 0:
    if plus % 2:
        sumMul += nums.get()

    div = plus // 2

    for _ in range(div):
        num1 = nums.get()
        num2 = nums.get()
        sumMul += num1*num2

print(sumMul)

 

 

 

기억할 점

• 1에 대한 처리가 필요하다는 사실을 몰라 시간이 걸렸다.
• 수열의 갯수가 홀수 일때 처리에도 애먹은 문제였다.