[baekjoon] 백준 1744번(파이썬): 수 묶기

문제

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보다 작은 자연수이다.

- 수열의 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

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

알고리즘

- 수열의 크기를 입력받는다.

- 양수, 음수와 0, 1 끼리 묶어주기 위해 리스트를 세 개 만들어 리스트에 수를 넣는다.

- 양수 리스트는 큰 수끼리 곱해주기 위해 내림차순으로 정렬한다.

- 음수, 0 리스트는 큰 수끼리 곱해주기 위해 오름차순으로 정렬한다. 

- 1 리스트는 곱하기보다는 더하는 게 더 최댓값이 나오기 때문에 결괏값에 모두 더한다.

- 양수 리스트에 있는 수는 묶어주고(곱하기) 결과값에 더한다.

- 음수, 0 리스트도 수를 묶어주어 결과값에 더한다.

코드

import sys
n = int(sys.stdin.readline())
# 양수 리스트
po = []
# 음수, 0 리스트
ne = []
# 1 리스트
one = []
# 수열의 합 초기값
result = 0

for _ in range(n):
    num = int(sys.stdin.readline())
    # 수열의 수가 1보다 크면 양수 리스트의 추가
    if num > 1:
        po.append(num)
    # 수열의 수가 0보다 작거나 같으면 음수, 0 리스트의 추가
    elif num <= 0:
        ne.append(num)
    # 수열의 수 1을 1 리스트의 추가
    else:
        one.append(num)
# 양수 리스트를 내림차순으로 정렬
po.sort(reverse=True)
# 음수, 0 리스트를 오름차순으로 정렬
ne.sort()

# 1은 곱하게 되면 그냥 그대로 이기때문에 묶지 않고 결과값과 바로 더해준다.
result += sum(one)

# 양수 리스트를 묶어서 결과값에 더해준다.
if len(po) % 2 == 0:
    for i in range(0, len(po), 2):
        result += po[i] * po[i+1]
else:
    for i in range(0, len(po)-1, 2):
        result += po[i] * po[i+1]
    result += po[-1]

# 음수 리스트를 묶어서 결과값에 더해준다.
# 음수를 묶으면 양수가 된다.
if len(ne) % 2 == 0:
    for i in range(0, len(ne), 2):
        result += ne[i] * ne[i+1]
else:
    for i in range(0, len(ne)-1, 2):
        result += ne[i] * ne[i+1]
    result += ne[-1]


print(result)

결과

위 코드에서 수를 받고 정렬을 한 후에 print(po, ne, one)을 작성하게 되면 리스트가 어떤 수를 입력받았고 정렬이 어떻게 되었는지 출력 화면과 같이 확인할 수 있다.

<출력화면>

위 출력 화면을 보게 되면 양수 리스트인 po 리스트에 양수인 3과 2가 내림차순으로 정렬되어 있는 것을 확인할 수 있고 음수, 0 리스트인 ne 리스트에 음수 -1이 있는 것을 확인할 수 있고 1 리스트인 one 리스트에 1이 있는 것을 확인할 수 있다. 따라서 양수 리스트를 묶어주면 6이 되고 음수, 0 리스트는 -1이 하나이기 때문에 묶을 필요가 없어 혼자 나오게 되고 one 리스트는 1을 결과값에 더해주면 된다. 따라서 식은 (-1)+1+(2*3) = 6 이 된다.

<출력화면>

위 다른 예시의 출력화면을 보게 되면 양수 리스트인 po 리스트에 양수인 3과 2가 내림차순으로 정렬되어 있는 것을 확인할 수 있고 음수, 0 리스트인 ne 리스트에 음수 -3과 -1, 0이 오름차순으로 정렬되어 있는 것을 확인할 수 있고 1 리스트인 one 리스트에 1이 있는 것을 확인할 수 있다. 따라서 양수 리스트를 묶어주면 6이 되고 음수, 0 리스트는 -3, -1, 0이기 때문에 -3과 -1을 묶어주고 0은 그냥 더해주고 one 리스트는 1을 결과값에 더해주면 된다. 따라서 식은 0+(-3*-1)+1+(2*3) = 10 이 된다.

따라서 코드를 분석하게 되면 수를 묶었을 때 수가 최대가 나오기 위해서 양수끼리는 무조건 곱해주거나 더해주어야 하고 음수끼리는 곱해주어 양수를 만들거나 0을 곱해주어 음수를 없애야 한다. 그리고 숫자 1은 곱하는 것보다 그냥 더하는 게 최대가 대기 때문에 숫자 1은 모두 더해주는 것이다.

github

junjange/CodingTest