1744 - 수 묶기
문제
길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.
예를 들면, 어떤 수열이 일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2X3)+(4X5) = 27이 되어 최대가 된다.
수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.
수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.
코드
N = int(input())
pos, neg, etc = [], [], []
for _ in range(N):
num = int(input())
if num > 1:
pos.append(num)
elif num < 0:
neg.append(num)
else:
etc.append(num)
pos.sort(reverse=True)
neg.sort()
result = 0
for i in range(1, len(pos), 2):
result += pos[i-1] * pos[i]
if len(pos) % 2 == 1:
result += pos[-1]
for i in range(1, len(neg), 2):
result += neg[i-1] * neg[i]
if len(neg) % 2 == 1:
if 0 not in etc:
result += neg[-1]
result += sum(etc)
print(result)한마디
수들을 세 가지 리스트로 나눠서 입력받았다.
- pos : 1보다 큰 수들
- neg : 0보다 작은 수들
- etc : 그 외 수들 (0과 1)
합이 최대가 되게끔 하려면 pos는 내림차순, neg은 오름차순으로 정렬해 두 수씩 곱해서 result 값에 더해줬다. neg 리스트에 홀수 개의 수가 들어있다면 etc 리스트에 0이 있는지 여부에 따라 추가해줄지 말지를 결정한다.
0이 있다면 음수를 더하는 것보다 곱해서 0을 만드는 것의 결과값이 더 크기 때문이다.
