[Beakjoon] 백준 2036번 Python

Beakjoon 2036, 수열의 점수
solved.ac Gold5
Greedy알고리즘

문제

n개의 정수로 이루어진 수열이 있다. 이 수열에서 한 정수를 제거하거나, 또는 두 정수를 제거할 수 있다. 한 정수를 제거하는 경우에는 그 정수가 점수가 되고, 두 정수를 제거하는 경우에는 두 정수의 곱이 점수가 된다. 이를 반복하여 수열에 아무 수도 남지 않게 되었을 때, 점수의 총 합의 최대를 구하는 프로그램을 작성하시오.

예를 들어 -1, 5, -3, 5, 1과 같은 수열이 있다고 하자. 먼저 1을 제거하고, 다음으로는 5와 5를 제거하고, 다음에는 -1과 -3을 제거했다고 하자. 이 경우 각각 점수가 1, 25, 3이 되어 총 합이 29가 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 절댓값이 1,000,000을 넘지 않는 정수가 n개 주어진다.

출력

첫째 줄에 최대 점수를 출력한다.

Solution

n = int(input())

dataM = []
dataP = []
data0 = []
for _ in range(n):
    m = int(input())
    if m == 0:
        data0.append(m)
    elif m > 0:
        dataP.append(m)
    else:
        dataM.append(m)

dataP.sort(reverse=True)
dataM.sort()

count = 0
while True:
    if len(dataP) > 1:
        if dataP[0] + dataP[1] > dataP[0] * dataP[1]:
            count += dataP[0] + dataP[1]
        else:
            count += dataP[0] * dataP[1]
        del dataP[1], dataP[0]
    if len(dataP) == 1:
        count += dataP[0]
        del dataP[0]
    
    if len(dataM) > 1:
        count += dataM[0] * dataM[1]
        del dataM[1], dataM[0]

    if len(dataM) == 1 and len(data0) == 0:
        count += dataM[0]
        del dataM[0]

    if len(dataP) == 0 and len(dataM) <=1:
        break
        
print(count)

풀이

0, 양의 정수, 음의 정수 리스트를 만든 다음 양의 정수는 내림차순, 음의 정수는 오름차순으로 정렬합니다.

양의 정수 리스트의 길이가 1보다 크면서 양의 정수의 가장 큰 두 값이 서로 더한 값이 더 크다면 count에 더한 값을, 곱한 값이 더 크면 곱한 값을 더해줍니다. 그리고 두 수를 리스트에서 지워줍니다. 이것을 반복하다가 양의 정수가 한 개만 남게 되면 그 수를 count에 더해줍니다.

음의 정수 리스트도 똑같지만 0의 리스트가 1개라도 있다면 마지막 음의 정수는 0과 곱하게 되어 그 수를 날려줍니다.

• dataM = [], dataP = [], data0 = [] : 음의 정수, 양의 정수, 0을 담을 리스트를 만들어줍니다.
• dataP.sort(reverse=True), dataM.sort() : 양의 정수는 내림차순, 음의 정수는 오름차순으로 정렬합니다.
• if dataP[0] + dataP[1] > dataP[0] * dataP[1] : 양의 정수의 더한 값과 곱한 값 중 더 큰 값을 비교합니다.
• if len(dataP) == 1: count += dataP[0] : 양의 정수가 한 개 남았을 때 count에 더해줍니다.
• if len(dataM) > 1: count += dataM[0] * dataM[1] : 음의 정수는 곱한 수를 count에 더해줍니다.
• if len(dataM) == 1 and len(data0) == 0 : 음의 정수가 한 개 남고, 0이 없는 경우를 찾습니다.
• if len(dataP) == 0 and len(dataM) <=1: break : 양의 정수가 한 개도 없고, 음의 정수가 1개 혹은 0개일 경우 break 합니다.

---

반례

음의정수 리스트가 1이 되자마자 break된 경우	서로 더한값이 곱한값 보다 큰경우	0을 처리하지 않았을 경우
3 -2 -2 -1	3 1 1 1	4 -1 -3 -2 0
3	3	6

2036번: 수열의 점수