백준 온라인 저널, 그리디 알고리즘/1744번 : 수 묶기(파이썬) / 백준 골드 문제

문제 정의

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.

 

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

 

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

 

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

 

 

입력

첫째 줄에 수열의 크기 N이 주어진다. N은 10,000보다 작은 자연수이다. 둘째 줄부터 N개의 줄에, 수열의 각 수가 주어진다. 수열의 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

 

 

출력

수를 합이 최대가 나오게 묶었을 때 합을 출력한다. 정답은 항상 231보다 작다.

 

 

예제 입력 1

4
-1
2
1
3

예제 출력 1

6

 

- 높은  숫자끼리 곱할수록 더 높은 숫자가 나온다.

 

 

접근 방법

1. 주어진 수열을 리스트(num)로 받아 절대값이 높은 순서대로 정렬한다.

2. 반복문을 사용해 수열의 낮은 인덱스부터(절대값이 높은 순서대로) 차례로 뽑아 0, 1, 음수, 양수인지에 따라 다르게 동작하도록한다. 이때 음수와 양수의 개수를 나타내는 리스트(count)와 음수 변수(num_n)와, 양수 변수(num_p)를 만든다.

3. 뽑은 원소가 0인 경우 더 이상 출력할 필요가 없으므로 반복문을 종료한다.(해당 원수보다 뒤에 있는 원소는 무조건 0)

4. 뽑은 원소가 1인 경우 더하는 것이 가장 최선의 선택이므로 결과 값(result)에 이를 더한다.

5. 뽑은 원소가 음수인 경우 음수 변수(num_n)에 곱해준다. 이때 음수 변수에 곱한 개수가 2개일 경우 음수 변수를 결과 값(result)에 이를 더해주고 음수 변수와 개수를 초기화한다.

6. 뽑은 원소가 양수인 경우 양수 변수(num_p)에 곱해준다. 이때 양수 변수에 곱한 개수가 2개일 경우 양수 변수를 결과 값(result)에 이를 더해주고 양수 변수와 개수를 초기화한다.

7. 반복문이 끝나면 결과 값을 출력한다.

 

코드

import sys
n = int(sys.stdin.readline())
num = [int(sys.stdin.readline()) for _ in range(n)]

# 절대값이 높은 순서대로 정렬한다.
num.sort(reverse=True, key=lambda x: abs(x))

num_n, num_p = 1, 1
count = [0, 0]
result = 0

for n in num:
    # n이 0인 경우 n이 음수일 때가 홀수인 경우 이를 곱하는 것이 더 큰 수를 만드므로 이를 확인한 후 break
    if n == 0:
        if count[0] == 1:
            num_n = 0
            count[0] = 0
        break
    # n이 1인 경우는 더하는 것이 더 이득이므로 이를 더한다.
    elif n == 1:
        result += 1

    # n이 음수인 경우 음수끼리 곱한다.
    elif n < 0:
        count[0] += 1
        num_n *= n

        # 이때 음수를 두번 곱할 경우 num_n과 count[0]을 초기화한다.
        if count[0] == 2:
            count[0] = 0
            result += num_n
            num_n = 1
    # n이 양수인 경우 양수끼리 곱한다.
    else:
        count[1] += 1
        num_p *= n
        if count[1] == 2:
            count[1] = 0
            result += num_p
            num_p = 1

for i in range(len(count)):
    if count[i] == 1 and i == 0:
        result += num_n
    elif count[i] == 1 and i == 1:
        result += num_p
print(result)