🟩 [백준] [Python] [Gold4] 1744번_수 묶기

문제

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

1744번: 수 묶기

풀이

# 백준 1744번 문제 - 수 묶기
n = int(input())

minus_list = []
plus_list = []
one_list = []
answer = 0
for i in range(n):
    num = int(input())
    if num <= 0:
        minus_list.append(num)
    elif num > 1:
        plus_list.append(num)
    else:
        one_list.append(num)
plus_list.sort(reverse=True)
minus_list.sort()

len_plus = len(plus_list)
len_minus = len(minus_list)

if len_plus % 2 == 1: # 홀수일 경우 
    answer += plus_list[-1]
    for j in range(0, len_plus-1, 2):
        answer += plus_list[j] * plus_list[j+1]
else:
    for j in range(0, len_plus, 2):
        answer += plus_list[j] * plus_list[j+1]

if len_minus % 2 == 1:
    answer += minus_list[-1]
    for j in range(0, len_minus-1, 2):
        answer += minus_list[j] * minus_list[j+1]
else:
    for j in range(0, len_minus, 2):
        answer += minus_list[j] * minus_list[j+1]
    
for i in one_list:
    answer += i

print(answer)

그리디 알고리즘에 분류되어 있는 문제이다. 

 

주의해야 할 점은 음수와 양수를 나누고 개수가 짝수인지 홀수인지 구분하는 것이다.

음수*음수 = 양수 가 되기 때문에 음수와 양수를 따로 리스트를 만들어 계산한다.

음수는 오름차순 정렬, 양수는 내림차순 정렬을 해준다. 

짝수라면 2개씩 묶어서 남는 부분이 없어서 모두 묶어서 더해주면 된다. 

반면 홀수라면  정렬을 해주어서 마지막 값이 가장 작은 값이기 때문에 남게 되는 마지막 값을 그냥 더해주면 된다. 

1은 곱하기 보다 더하는 것이 더 효율적이기 때문에 1은 따로 더해주도록 한다.