[Python 알고리즘] 백준 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은 50보다 작은 자연수이다. 둘째 줄부터 N개의 줄에 수열의 각 수가 주어진다. 수열의 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

# Case 1
4
-1
2
1
3


# Case 2
6
0
1
2
4
3
5


# Case 3
1
-1


# Case 4
3
-1
0
1


# Case 5
2
1
1

출력

# Case 1
6


# Case 2
27


# Case 3
-1


# Case 4
1


# Case 5
2

내가 제출한 풀이 - 정답

import sys

n = int(sys.stdin.readline().strip())
n_list = [int(sys.stdin.readline().strip()) for _ in range(n)]
n_list.sort()

zero_cnt = 0
positive_list = []
negative_list = []

for i in range(0, len(n_list)):
    if n_list[i] == 0:
        zero_cnt += 1
    elif n_list[i] < 1:
        negative_list.append(n_list[i])
    else:
        positive_list.append(n_list[i])

for i in range(0, zero_cnt):
    if len(negative_list) == 1:
        negative_list.pop(0)
    elif len(negative_list) % 2 == 1:
        negative_list.remove(max(negative_list))

res1 = 0
res2 = 0

for i in range(0, len(negative_list), 2):
    if i + 1 == len(negative_list):
        res1 += negative_list[i]
    else:
        res1 += max(negative_list[i] * negative_list[i + 1], negative_list[i] + negative_list[i + 1])

for i in range(len(positive_list) - 1, -1, -2):
    if i - 1 == -1:
        res2 += positive_list[i]
    else:
        res2 += max(positive_list[i] * positive_list[i - 1], positive_list[i] + positive_list[i - 1])

print(res1 + res2)

문제 풀이

이번 문제는 이러한 경우의 수가 있다.

1. 양수는 큰 숫자끼리 곱하는 것이 좋다.
2. 음수는 큰 숫자끼리 곱하는 것이 좋다. 왜냐하면, 음수끼리 곱하면 양수가 되기 떄문이다. ex) -50 * -50 = 2500
3. 음수 1개 및 0이 있다면 둘이 곱해 0을 만들어주는 것이 좋다.
4. 음수가 홀수 개 및 0이 있다면 가장 큰 음수를 제거하는 것이 좋다.
5. 1 * 1, 0 * 1, 2 * 1 ... 보단 1 + 1, 0 + 1, 2 + 1 ...이 더 높다.

입력이 이러한다고 가정한다.

5
-537
81
-435
257
157

 

n_list = [int(sys.stdin.readline().strip()) for _ in range(n)]
n_list.sort()

zero_cnt = 0
positive_list = []
negative_list = []

for i in range(0, len(n_list)):
    if n_list[i] == 0:
        zero_cnt += 1
    elif n_list[i] < 1:
        negative_list.append(n_list[i])
    else:
        positive_list.append(n_list[i])
        
# positive_list = [81, 157, 257]
# negative_list = [-537, -435]

양수, 음수의 큰 숫자를 쉽게 얻기 위해 음수 리스트, 양수 리스트로 나누어 저장한다.

그리고, 0은 음수를 곱해 0을 만들수도 있기 때문에 따로 카운트를 올려 저장한다.

 

for i in range(0, zero_cnt):
    if len(negative_list) == 1:
        negative_list.pop(0)
    elif len(negative_list) % 2 == 1:
        negative_list.remove(max(negative_list))

 

음수 리스트의 길이가 1이라면 음수 * 0을 하여 음수를 없앤다.

음수 리스트가 홀수 개라면 음수 리스트에서 가장 큰 수를 삭제한다.

음수 * 음수는 음수가 작아질 수록 양수가 더 커지기 때문이다.

 

res1 = 0
res2 = 0

# 음수리스트 결과 값 저장
for i in range(0, len(negative_list), 2):
    if i + 1 == len(negative_list): # 마지막 수는 더하기
        res1 += negative_list[i]
    else: # 곱하기 또는 더하기 둘 중 더 큰 수를 더하기
        res1 += max(negative_list[i] * negative_list[i + 1], negative_list[i] + negative_list[i + 1])

# 양수리스트 결과 값 저장
for i in range(len(positive_list) - 1, -1, -2):
    if i - 1 == -1: # 마지막 수는 더하기
        res2 += positive_list[i]
    else: # 곱하기 또는 더하기 둘 중 더 큰 수를 더하기
        res2 += max(positive_list[i] * positive_list[i - 1], positive_list[i] + positive_list[i - 1])

print(res1 + res2)

# res1 = -537 * -435
# res2 = 81 + (257 * 157)
# res1 = 233595
# res2 = 40430
# res1 + res2 = 274025

음수 리스트, 양수 리스트 각각 2개씩 짝지어서 봐야한다.

양수리스트에선 i == len(list) 인 경우와 음수리스트에선 i - 1 == -1인 경우에는 곱하기를 할 수 없기 때문에 무조건 더해주어야 한다.

나머지는 list[i] + list[i + 1]와 list[i] * list[i + 1]를 비교해 더 큰 수를 변수에 더해준다.

 

그렇게 어렵지 않은 문제였다.