[Python] 백준 1744번 : 수 묶기

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

1744번: 수 묶기

---

💡 문제 풀이

그리디 알고리즘 문제이다.

수를 묶는 기준을 가장 큰 값이 되는 기준을 찾아내면 된다.

 

같은 부호끼리는 곱해도 되지만 부호가 다르면 그냥 더하는게 곱하는 것보다 큰 값이 나온다.

0은 양수는 더하는게 크지만 음수는 곱하는게 더 큰 값이 나온다.

1은 양수, 음수 모두 더하는게 더 큰 값이 나온다.

 

이런 이유로 입력받는 값들을 나누어줘야하는데 음수(+ 0), 양수, 1로 나눠서 입력받는다.

0을 음수 쪽에 저장하는 이유는 음수가 하나 밖에 없는 경우 0과 곱해줘서 없애버리는게 가장 큰 값이 나오기 때문이다.

 

부호가 나뉘었으니 정렬을 해주고 2개씩 뽑아서 곱한 값을 결과값에 더해주면 된다.

만약 개수가 홀수라면 마지막 것은 그냥 더해주면 된다.

✔️ 느낀 점

딱 보자마자 느낌이 와서 구현했다. 처음 코드가 너무 지저분해서 리팩토링을 나름 했는데도 지저분한 것 같다.

💻 코드

N = int(input())
positive, negative = [], []
one = []

for _ in range(N):
    tmp = int(input())
    if tmp > 1: positive.append(tmp)
    elif tmp <= 0: negative.append(tmp)
    else: one.append(tmp)
    
positive.sort(reverse=True)
negative.sort()

result = sum(one)

def solution(array):
    global result
    
    l = len(array)
    for i in range(0, l, 2):
        if i == l-1:
            result += array[i]
            break
        result += array[i] * array[i+1]
    
for arr in [positive, negative]:
    solution(arr)

print(result)