알고리즘 스터디 - 백준 2036번 : 수열의 점수

문제 해석

• n개의 수열에서 하나를 제거하거나 두 개의 정수를 제거할 수 있음
• 하나만 제거하면 제거한 정수 = 점수 / 두 개를 제거하면 두 정수의 곱 = 점수
• 이렇게 반복하여 아무 수도 남지 않았을 때 점수의 총합이 최대인 프로그램을 구해야 함

어떤 알고리즘을 사용해야 할까?

수 묶기의 규칙을 이용해 그리디 알고리즘을 사용해보자

• 그리디 알고리즘의 대표적인 동전 문제를 살펴 보면 항상 큰 값부터 보면서 값을 찾아가는 방식이다.
• 여기서, [5, 5, 5, 1, -1, -3] 이라고 하면 큰 값부터 2개를 뽑아서 곱하고 더하고 그 다음 큰 값은 곱했을 때 자기 자신이므로 곱하지 않고 더한다. 그리고 더하고 음수가 2개만 남았을 때 2개를 곱하면 양수이기에 이 가장 작은 음수 2개를 뽑아 더하게 된다.

규칙 1 : 양수, 양수 = 곱셈 / 음수, 음수 = 곳셈 / 양수, 음수 = 덧셈
규칙 2 : 0, 양수 = 덧셈 / 0, 음수 = 곱셈
규칙 3 : 1, 양수 = 덧셈 / 1, 음수 = 덧셈

수열을 받고
양수 음수로 분리
양수는 내림차순, 음수는 오름차순으로 정렬
각 분리한 리스트를 그리디 탐색으로 실행해 도출

알고리즘 코드

N = int(input())

# 양수, 음수, 1을 분리
positive=[]
negative=[]
one=[]

for _ in range(N):
    num = int(input())
    if num > 1:
        positive.append(num)
    elif num <= 0:
        negative.append(num)
    else:
        one.append(num)

# 그리디 탐색에 맞게 양수는 내림차순, 음수는 오름차순으로 정렬
positive.sort(reverse=True)
negative.sort()

# 결과
result = 0

# 양수 리스트 입력
# 짝수일때
if len(positive) % 2 == 0:
    for i in range(0,len(positive),2):
        result += positive[i] * positive[i+1]
# 홀수일때
else:
    for i in range(0,len(positive)-1,2):
        result += positive[i] * positive[i+1]
    result += positive[len(positive)-1]

# 음수 리스트 입력
# 짝수일때
if len(negative) % 2 == 0:
    for i in range(0,len(negative),2):
        result += negative[i] * negative[i+1]
# 홀수일때
else:
    for i in range(0,len(negative)-1,2):
        result += negative[i] * negative[i+1]
    result += negative[len(negative)-1]

result += sum(one)

print(result)