[BOJ 1744, Python 3] 수 묶기

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

1744번: 수 묶기

 

풀이

간단한 그리디 + case work 문제 같습니다.

 

1. 1을 제외한 양수

양수에서 큰 값 2개를 계속 곱하다가 나중에 1개만 남으면 남은 한 개는 더해주면 됩니다.

 

2. 1일 때

1 * 7 보다 1 + 7이 더 크기 때문에 1은 전부 더해주기만 합니다.

 

3. 음수의 개수가 짝수일 때

제일 작은 수 2개끼리 계속 곱해주면 됩니다.

 

4. 음수의 개수가 홀수일 때

3번처럼 제일 작은 수 2개끼리 곱해줘서 1개가 남기면 됩니다.

이 1개는 수열에 0이 있으면 (음수) * 0 = 0으로 만들 수 있습니다.

하지만 수열에 0이 없으면 음수를 답에 더해줘야 합니다.

 

 

 

1의 경우를 생각 못해서 많이 틀리다가 통과했네요

 

 

코드

n = int(input())
arr = [int(input()) for _ in range(n)]
plus = sorted([arr[i] for i in range(n) if arr[i] > 1])
minus = sorted([arr[i] for i in range(n) if arr[i] <= 0], reverse=True)
zero = [arr[i] for i in range(n) if arr[i] == 0]
one = [arr[i] for i in range(n) if arr[i] == 1]
ans = 0
while plus:
    x = plus.pop()
    if not plus: ans += x
    else: ans += x * plus.pop()
while len(minus) > 1:
    x = minus.pop()
    if minus: ans += x * minus.pop()
ans += len(one)
if not zero and minus: print(ans + minus[0])
else: print(ans)