[python] 백준1744번 : 수 묶기

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

1744번: 수 묶기

 

 

문제를 풀기 위해 생각한 아이디어

- 음수가 나올 경우 접근 우선 순위  1) 음수 * 음수

                                                            2) 음수 * 0 

                                                            3) 음수 내버려두기

- 양수가 나올 경우  1) 양수 * 양수 ( 단, 두 양수 모두 1이면 안됨 -> 하나라도 1이라면 그냥 더해주는 게 낫다) 

                                                     ex. 1 3    1*3 < 1+3 

 

쉽게 풀기 위해서 0과 양수, 음수 배열을 따로 두어 관리하며 풀이하였다.

n = int(input())
zero, positive, negative = [], [], []
for _ in range(n):
    num = int(input())
    if num == 0: zero.append(num)
    elif num > 0: positive.append(num)
    else: negative.append(num)
negative.sort()
positive.sort()
result = [] # 그리디하게 구한 부분합들을 저장할 리스트 
while negative:
    num1 = negative.pop(0)
    # 음수 - 음수 짝이 있다면
    if negative:
        num2 = negative.pop(0)
        result.append(num1*num2)
    else:
        # 음수 - 0 짝이 있다면
        if zero:
            zero.pop()
        else:
            result.append(num1)
while positive:
    num1 = positive.pop()
    if num1 == 1:
        result.append(num1)
        continue
    # 양수 - 양수 짝이 있다면
    if positive:
        num2 = positive.pop()  
        if num2 == 1:
            result.append(num1)
            result.append(num2)
            continue
        result.append(num1*num2)
    else:
        result.append(num1)
print(sum(result))

 

처음 실패한 반례) num2에서 1인지 검사하는 조건을 빼먹어서 틀림.

                        다음과 같은 반례가 올 경우, num2이 1인지 검사해서 1이라면 num1과 곱하지 말고 result에 저장한다.

6
5
4
3
1
1
1