[Python] 그리디- 1744. 수 묶기(골4)

 

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

 

>> 문제 포인트

 

- 양수의 경우 큰수부터 두개씩 묶기

positive = [5,4,3,2] => 5*4 / 3*2

 

-1의 경우는 곱하면 아무 이득이 없으므로 묶지말고 더해주기

 

- 음수의 경우 절대값이 큰 수부터(작은수부터) 두개씩 묶기

negative = [-5, -4, -3, -2] => -5 *-4 / -3*-2

 

-음수를 두개씩 묶고 하나가 남았을 때,

=> 0이 나왔었다면 0이랑 곱해서 없애주는게 이득

=> 0이 안나왔었다면 그냥 더함

 

 

 

 

#1744

#0인 경우-> 포함x

#음수와 양수를 따로 모으기

 

positive=[]

negative=[]

result=0

n= int(input())

flag=0

for _ in range(n):

  k= int(input())

 

# 1의 경우 곱하면 아무 이득이 없으므로 더해주기

  if k==1:

    result+=1

  elif k>1:

    positive.append(k)

#2개씩 묶어 음수 1개가 남았다면 더하기보다 0이랑 곱해주는게 이득(negative에 0포함)

  else:

    negative.append(k)

#양수는 큰수부터 2개씩 묶기

positive= sorted(positive, reverse=True)

 

#음수는 절대값이 큰 수부터 2개씩 묶기

negative= sorted(negative)

for i in range(0, len(positive), 2):

  if i+1 >= len(positive):

    result+=positive[i]

  else:

    result+=positive[i]*positive[i+1]

for i in range(0, len(negative), 2):

  if i+1 >= len(negative):

    result+=negative[i]

  else:

    result+=negative[i]*negative[i+1]

print(result)