백준 - [Gold 4] 1744번 수 묶기

문제링크: www.acmicpc.net/problem/1744

1744번: 수 묶기

골드 4여서 두려웠지만, 경우의 수만 잘 따져주면 되는 문제였습니다.

---

문제 설명

- N: 숫자의 개수

- N개의 숫자가 주어진다.

- 숫자를 2개씩 묶을 수 있다. 묶은 수는 곱하기로 계산된다.

- 숫자는 단 한번만 묶거나 안 묶인다.

- ex) -1, 2, 3, 1 이 주어졌을 때 최대의 값은 (-1)+1+(2*3)=6 이다.

---

풀이

처음에는 단순하게 정렬하여 양수의 큰 수 끼리 곱 음수의 작은 수 끼리 곱으로 계산하였습니다. 역시나 실패하였고, 원인을 찾아본 결과 0과 1이 문제였습니다.

ex)

• -2 * 0 = 0
• -2 + 0 = -2
• 0 * 2 = 0
• 0 + 2 = 2
• 1 * 2 = 2
• 1 + 2 = 3

결론

0은 음수와 곱해지면 최대가 됩니다. 음수 부분에 포함하여 계산하면 됩니다.

1은 더하는 것이 무조건 크므로 제외하고 마지막에 더해주면 됩니다.

from sys import stdin

stdin = open("input.txt", "r")

# 숫자 개수
N = int(stdin.readline())

numbers = [int(stdin.readline()) for _ in range(N)]

numbers.sort()
answer = 0
left = 0
right = N - 1

if N == 1:
    print(numbers[0])
else:
    # 음수
    i = 0
    while left < right:
        if numbers[left] < 1 and numbers[left+1] < 1:
            answer += (numbers[left] * numbers[left+1])
            left += 2
        else:
            break
    # 양수
    while right > 0:
        if numbers[right] > 1 and numbers[right-1] > 1:
            answer += (numbers[right] * numbers[right-1])
            right -= 2
        else:
            break
    # print(numbers, left, right)
    # 나머지
    answer += sum([numbers[i] for i in range(right, left-1, -1)])

    print(answer)

코드: github.com/smothly/Algorithm_Solving/blob/master/boj-1744.py