[Python 3] BOJ 2036 수열의 점수

 

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

2036번: 수열의 점수

오늘 볼 문제는 수열의 점수라는 문제이다.

 

해당 문제는 한 개의 숫자를 제거해서 정답에 더하거나, 두 개의 숫자를 제거해서 제거한 두 숫자를 곱한 것 정답에 더할 수 있다. 이 점수의 합의 최대값을 구하면 된다.

 

 

n=int(input())
pos=[]
neg=[]
zero=0
one=0
for _ in range(n):
    num=int(input())
    if num>1:
        pos.append(num)
    elif num<0:
        neg.append(num)
    elif num==1:
        one+=1
    else:
        zero=1

pos.sort()
neg.sort(reverse=True)

answer=0
while pos:
    if len(pos)>=2:
        a=pos.pop()
        b=pos.pop()
        answer+=a*b
    else:
        answer+=pos.pop()

while neg:
    if len(neg)>=2:
        a=neg.pop()
        b=neg.pop()
        answer+=a*b
    else:
        if zero:
            break
        else:
            answer+=neg.pop()

answer+=one
print(answer)

 

각 숫자를 4가지 종류로 나눌 수 있다.

0, 1, 1을 제외한 양수, 음수

 

0: 그냥 더하면 0이지만, 음수 한 개를 0과 곱하면 해당 수가 0이 된다. (음수로 정답이 마이너스가 되는 걸 막을 수 있다.)

1: 1은 1이 아닌 양수랑 곱하면 같은 수를 주기 때문에, 1을 따로 더하는게 이득이다. 예를 들어, 1과 3이 있음, 곱하면 3이다. 하지만 따로 더하면 1, 3을 더하기에 4를 더할 수 있다. 1은 곱하면 안 된다.

1을 제외한 양수: 제일 큰 양수들끼리 곱한다. 만약 한 개 남으면, 그냥 더한다.

음수: 제일 작은 양수들끼리 곱한다. 만약 한 개 남으면, 0이 있으면 0과 곱하고, 0이 없으면 그냥 더한다.

 

값들을 받을 때, 각자 카테고리에 맞게끔 저장한다. 1을 제외한 양수, 음수는 정확한 값을, 0은 있는지 없는지 여부, 1은 1의 개수를 센다. 이후 1을 제외한 양수는 오름차순, 음수는 내림차순을 한다. 이후 2개씩 pop 하고 곱하여 정답에 더해준다. 한개가 남았을 때는 따로 처리해서 더해준다.

 

굉장히 직관적이고 쉬워보이는 문제였는데, 코너케이스가 신박해서 재미있던 문제였다.