수 묶기

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

1744번: 수 묶기

문제요약:

수열이 주어졌을 때, 수열은 그냥 더해도 되고 두개씩 쌍을지어 그 곱을 더해도 된다.

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

 

난이도:

골드4

 

소요시간:

20분

 

제출횟수:

1회

 

코딩:

import sys
from bisect import bisect_left,bisect_right
input = sys.stdin.readline

n = int(input())
arr = [int(input()) for _ in range(n)]

arr.sort()
piv1,piv2 = bisect_left(arr,0),bisect_right(arr,0)
count_0 = piv2-piv1
#0의 개수
arr1,arr2 = arr[:piv1],arr[piv2:]
#음수와 양수
arr2 = arr2[::-1]

S = 0 
for i in range(0,len(arr2)-1,2):
    if arr2[i]!=1 and arr2[i+1]!=1:
        S+=arr2[i]*arr2[i+1]    
    else:
        #둘중에 하나라도 1이라면 곱하는거보다 더하는게 더 큼
        S+=arr2[i]+arr2[i+1]  
    
for i in range(0,len(arr1)-1,2):
    S+=arr1[i]*arr1[i+1]
    
if len(arr2)%2:
    #남은 양수가 있다면 더해주기
    S+=arr2[-1]
    
if len(arr1)%2 and not count_0:
    #마이너스가 남은게 있는데 하필 0은 남은게 없으면
    S+=arr1[-1]
print(S)

그리디하게 푼 문제 입니다. 두개씩의 합을 가장 크게 하려면 큰값들부터 두개씩 사용해야 하므로, sort를 통해 정렬시켜준뒤 0을 기준으로 음수 양수 list를 만들어 줍니다. 그 후, 양수부터 큰 값 두개씩 곱해서 총합 S에 더해주고, 음수도 작은값(절대값이 큰값이 두개 곱해지면 가장큰 양수의 값이 되므로)부터 두개씩 곱해서 더해줍니다. 이후 만약 양수가 홀수여서 하나가 남게 된다면 따로 더해주고, 음수가 만약 홀수일때 0이 없다면 무조건 더해주어야 하지만, 0이 있다면 곱해서 없앨수 있기 때문에 음수가 홀수여서 더해주지 않은 남은게 있고 0이 하나도 없을때만 S에 나머지 값을 더해줍니다.

 

사실 설명을 안하고 넘어간 부분이 있는데, 양수에서 if,else구문이 있습니다. 주석에도 달아놨지만 양수가 두개 있을때 만약 두 양수중 하나가 1이라면 A+1>A*1 로 더하는것이 곱하는것보다 크기 때문에 이때는 곱하지 않고 더한값을 더해줍니다. 사실 이부분은 제가 스스로 찾은게 아니라 제공된 예시를 넣다 발견했기 때문에 만약 예시에서 제공되지 않았다면 빼먹을 뻔했으므로 , 다음에 이와같이 그리디문제들을 풀때, 또는 예외를 신경써야 할때, 빼먹은 것이 없는 지 잘 살펴봐야할 필요가 있습니다.