[백준 1744 : PYTHON] 수 묶기

문제 풀기 : 1744번

1744번: 수 묶기

문제

길이가 N인 수열이 주어졌을 때, 수열의 두 수를 묶고 수열의 합을 구한다.

위치에 상관없이 수를 묶을 수 있다.

같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다.

묶은 수는 서로 곱한 후에 더한다.

예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2x3)+(4x5) = 27이 되어 최대가 된다.

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

수열의 각 수를 적절히 묶었을 때, 그 합의 최대를 구한다.

문제풀이

최적의 해를 구하는 그리디 문제이다.

이 문제는 양수와 음수, 0과 1을 생각해 주어야한다.

• 양수의 경우 가장 큰 수를 기준으로 정렬하여 곱했을 때, 큰 값이 나온다.

• 음수의 경우 가장 작은 수를 기준으로 정렬하여 곱했을 때, 큰 값이 나온다. (-3, -2, -1,.. 순)

• 1은 무조건 더해주는 것이 수를 크게 만든다.

• 0의 경우는 음수들을 다 묶고 남은 것이 있을 때 그 값을 더하게 되면 결과값이 작아지므로 마지막으로 남은 음수값을 0과 곱한다.

  • 남은 음수값과 0을 곱하기 위해선 0을 음수 데이터 배열에 넣어주면 된다. 가장 끝에 배치되므로 0이 남으면 더해지고 남는 음수값이 생기면 자동으로 곱해진다.

전체코드

# n : 데이터의 크기
n = int(input())

# plus : 양수 데이터 리스트, minus : 음수 데이터 리스트
plus = []
minus = []

result = 0
for i in range(n):
    num = int(input())
    if num > 1:
        plus.append(num)
    elif num <= 0:
        minus.append(num)
    else:
        result += num

# 정렬
plus.sort(reverse=True)
minus.sort() # ex) -3 -2 -1 

# 양수 묶기
for i in range(0, len(plus), 2):
    if i+1 >= len(plus):
        result += plus[i]
    else:
        result += (plus[i] * plus[i+1])

# 음수 묶기
for i in range(0, len(minus), 2):
    if i+1 >= len(minus):
        result += minus[i]
    else:
        result += (minus[i] * minus[i+1])

print(result)