백준: 1744 수 묶기

문제

1744번: 수 묶기

 

문제 풀이

 수열의 두 수를 묶어 곱한 후에 각각의 값들 합할 때, 최댓값이 되는 값을 반환하는 문제이다. 문제를 풀기 위해서는 음수는 음수 별로 곱하여 양수로 만들어주고, 0과 1에 대해 별도로 처리해 주어야 할 필요가 있다.

 

• 입력되는 숫자들을 음수, 양수, 0, 1로 분리한다.
• 0의 경우 존재 여부만 확인하면 되지만, 1의 경우 몇개가 존재하는지 확인하여야 한다.
  • 1은 다른 수와 곱해도, 같은 수이므로 묶지 않고 더하는 것이 큰 수를 만들 수 있다.
  • 0이 있을 경우, 음수가 홀수로 입력되었을 때 하나를 0으로 만들어 상쇄시킬 수 있다.
• 음수의 경우 가장 작은 값 부터 묶어서 곱한다.
• 양수의 경우 가장 큰 값 부터 묶어서 곱한다.

 

코드

from sys import stdin


if __name__ == "__main__":
    n = int(stdin.readline())
    answer = 0
    minus, plus, zero, one = [], [], 1, 0
    for i in range(n):
        num = int(stdin.readline())
        if num > 1:
            plus.append(num)
        elif num == 1:
            one += 1
        elif num < 0:
            minus.append(num)
        else:
            zero = 0
            
    minus.sort(reverse=True)
    plus.sort()

    # 1은 곱해도 소용 없으므로 더한다.
    if one:
        answer += one

    while len(minus) > 1:
        a, b = minus.pop(), minus.pop()
        answer += a * b

    while len(plus) > 1:
        a, b = plus.pop(), plus.pop()
        answer += a * b

    # 만약 음수가 남고 0이 있는 경우, 곱하여 상쇄 시킨다.
    answer += minus[0] * zero if minus else 0
    answer += plus[0] if plus else 0

    print(answer)

 55~57%쯤에서 계속 틀렸다고 하여서, 뭐가 틀렸지 하고 반례들을 생각해보았는데 0일 경우에는 개수를 확인하지 않아도 되지만, 1일 경우 몇 개가 입력되었는지 확인하고 이를 반영해줘야 한다는 것을 알고 수정하니 맞았습니다를 볼 수 있었다.😊