[백준/Python]1744: 수 묶기

문제

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

백준 문제집 - 0x11강 - 그리디

 

알고리즘: 그리디, 정렬

---

풀이

문제길이가 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이 되어 최대가 된다.

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.
수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

수의 범위는 -1,000 ~ 1,000 이다.

따라서 음수와 양수가 섞여있는 수열이 주어질 수도 있으므로 조건분기를 확실히 해야한다.

먼저 수열을 오름차순으로 정렬 후 음수, 양수, 0, 1 로 분리시킨다. 그럼 분리시킨 항목들은 자연스럽게 오름차순이 된다.

 

최대값을 만들기위한 조건은 아래와 같다.

- 음수는 최대한 0에 가깝게, 혹은 양수로 만들어준다.

- 양수는 큰 값끼리 곱해준다.

- 0은 양수와는 사용하지 않는다. 음수와 짝지어서 상쇄시키거나 사용하지 않는다.

- 1은 그대로 둔다.

 

1. 음수값 처리

갯수에 따라 실행값이 달라진다.

홀수개, 한개 존재할경우는 0의 유무에 따라 분리된다.

 

1) 짝수개 존재할경우: 순서대로 두개씩 묶어 곱해준 뒤 결과값에 더해준다.

2) 홀수개 존재할경우: 제일 큰 값(양수에 가까운 값)을 제외하고 순서대로 두개씩 곱해준다.

- 0이 있을경우: 위의 제일 큰 값과 0을 곱해 0으로 만들어준 뒤 0의 갯수를 감소시킨다.

- 0이 없을경우: 그대로 결과값에 더해준다.

3) 한 개 존재할경우

- 0이 있을경우: 0과 곱해줘서 0으로 만들어준 뒤 0의 갯수를 감소시킨다.

- 0이 없을경우: 그대로 결과값에 더해준다.

 

2. 양수값 처리

양수 역시 갯수에 따라 실행값이 달라진다.

단, 0은 양수와는 사용하지 않으므로 양수값이 1개인 경우는 체크하지 않는다.

 

1) 짝수개 존재할경우: 순서대로 두개씩 묶어 곱해준 뒤 결과값에 더해준다.

2) 홀수개 존재할경우: 제일 작은값은 그대로 더해주고, 나머지는 두개씩 묶어 곱해준다.

 

3. 나머지

여태까지의 결과값에 1의 갯수만큼을 더해준다.

0은 음수 처리 외엔 계산할 필요 없으므로 넘어간다.

 

전체 코드

# 메모리: 32412KB / 시간: 36ms
from sys import stdin


input = stdin.readline

N = int(input())
nums = [int(input()) for _ in range(N)]
nums.sort()
ret = 0

minus = []
plus = []
zero = 0
one = 0

for n in nums:
    if n < 0:
        minus.append(n)
    elif n == 0:
        zero += 1
    elif n == 1:
        one += 1
    else:
        plus.append(n)

# 1. 음수값 처리
if minus:
    if len(minus) % 2 == 0:
        for i in range(0, len(minus), 2):
            ret += minus[i] * minus[i+1]
    elif len(minus) == 1:
        if zero > 0:
            zero -= 1
        else:
            ret += minus[0]
    else:
        for i in range(0, len(minus)-1, 2):
            ret += minus[i] * minus[i+1]
        if zero > 0:
            zero -= 1
        else:
            ret += minus[-1]

# 2. 양수값 처리
if plus:
    if len(plus) % 2 == 0:
        for i in range(0, len(plus), 2):
            ret += plus[i] * plus[i+1]
    else:
        for i in range(len(plus)-1, 0, -2):
            ret += plus[i] * plus[i-1]
        ret += plus[0]

# 3. 나머지
print(ret + one)

피지컬 문제에 가깝다. 삐끗하면 다른 값이 나오므로 조건 작성시 주의해야한다.