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

백준 1744번 - 수 묶기

문제 바로가기

 

 

 

🙄 문제 이해

수열에서 자기 자신을 제외한 두 수를 골라서 묶습니다.

묶은 수는 서로 곱해서 누적합니다.

 

수열의 모든 수는 단 한번만 묶거나, 묶지 않아야 합니다.
합이 최대가 되도록 하는 묶기 방법을 찾는 것이 관건입니다.

 

{0, 1, 2, 4, 3, 5} 수열이 있을 때 총 두가지 경우가 가능합니다.

 

0+1+2+4+3+5 = 15
0+1+(2*3)+(4*5) = 27

 

최대값인 27을 만드는 것이 목표입니다.

 

 

 

📝 문제 풀이

 

문제를 풀 때 고려해야할 포인트를 아래와 같이 체크했습니다.

- 2개의 음수를 곱하면 양수가 됨
- 음수와 0을 곱하면 0이 됨
- 양수 2개 중 1이 있다면 곱해도 최댓값 x

 

따라서 0과 1의 유무, 양수의 갯수, 음수의 갯수를 고려해야 합니다.

 

 

복잡한 알고리즘은 없지만 분기에 따른 구현 내용이 많아 대략적인 흐름을 정하고 설계했습니다.

 

내림차순 정렬

음수의 갯수를 먼저 체크
음수 : 짝수면 다 곱해서 최댓값
       홀수면 가장 큰 하나만 놔두고 다 곱함
       -> 이때 0이 있다면 곱해서 날림
       -> 0이 없다면 어쩔수 없이 더해야함
이렇게 음수 전부 제거

0이 여러개일 경우
- whlie문으로 zero가 0이 될때까지 pop

1은 무조건 더해야함
1이 여러개일 경우 대비해 while문으로 one이 0될때까지 pop

음수,0,1을 제외한 양수만 남은 상황

양수가 짝수개 -> 두개씩 다 묶음
양수가 홀수개 -> 가장 작은 하나 pop해서 더하고 나머지 두개식 묶음

 

 

💻 Python 코드

#백준 1744 수 묶기

n = int(input())
arr = []
for i in range(n):
    arr.append(int(input()))

#음수가 짝수개인지 홀수개인지 체크
plus = []
minus = []
zero = []
one = []
for num in arr:
    if num > 1:
        plus.append(num)
    elif num == 1:
        one.append(num)
    elif num == 0:
        zero.append(num)
    else:
        minus.append(num)

total = 0

#1. 음수 제거
minus.sort()
if len(minus)%2==1: #음수가 홀수개
    temp = minus.pop()
    if len(zero) > 0:
        zero.pop()
    else:
        total += temp

while len(minus) > 0: #음수 제거
    a = minus.pop()
    b = minus.pop()
    total += a*b

#2. 0 제거(0이 여러개일 수도 있음)
while len(zero) > 0:
    zero.pop()

#3. 1 제거(1도 여러개일 수 있음)
while len(one) > 0:
    one.pop()
    total += 1

#4. 양수 갯수 확인
plus.sort(reverse=True)
if len(plus)%2==1:
    total += plus.pop()

while len(plus) > 0:
    a = plus.pop()
    b = plus.pop()
    total += a*b

print(total)