백준 1744 - 파이썬

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

1744번: 수 묶기

 

문제 풀이

이 문제는 규칙을 찾는 게 중요한 문제이다. 처음에는 입력된 값을 내림차순으로 정렬한 후 수를 묶어주면 최댓값을 구할 수 있겠다고 생각했다. 하지만 음수가 짝수개일 경우에는 해당되지 않았기에 양수와 음수를 분리해 계산하기로 했다. 하지만 이 경우도 예외가 있었는데, 0과 음수가 포함된 경우에는 최댓값을 구하지 못한다는 점이었다. 다음은 이에 대한 코드이다.

 코드

import sys
import heapq
input = sys.stdin.readline

plus_list = []
minus_list = []

n = int(input())

for _ in range(n):
  num = int(input())
  if num < 0:
    heapq.heappush(minus_list, -num)
  else:
    heapq.heappush(plus_list, -num)

result = []
arr = plus_list + minus_list

while True:
  if len(plus_list+minus_list) == 0:
    break

  if len(plus_list) != 0:
    if len(plus_list) == 1:
      a = -heapq.heappop(plus_list)
      result.append(a)
      continue
      
    plus_a = -heapq.heappop(plus_list)
    plus_b = -heapq.heappop(plus_list)
    
    plus_sum = plus_a + plus_b
    plus_mul = plus_a * plus_b

    if plus_sum < plus_mul:
      result.append(plus_mul)
    else:
      result.append(plus_sum)
      
  if len(minus_list) != 0:
    if len(minus_list) == 1:
      result.append(-heapq.heappop(minus_list))
      continue
    minus_a = -heapq.heappop(minus_list)
    minus_b = -heapq.heappop(minus_list)

    minus_sum = minus_a + minus_b
    minus_mul = minus_a * minus_b

    if minus_sum < minus_mul:
      result.append(minus_mul)
    else:
      result.append(minus_sum)
    

ans = 0
print(result)
for i in result:
  ans += i

print(ans)

최대힙을 사용하여 풀고자 했고, 위에서 말한 대로 양수와 음수를 구분해 계산하고자 했다. 하지만 백준 예제 4를 입력 시 0이 출력되었는데 0을 양수라고 생각하고 수를 묶었기 때문에 생긴 문제였다. 하루 정도 시간을 들인 문제이기에 다른 사람들의 블로그를 참고해 보기로 했다.

 

이 블로그에서는 규칙을 아래와 같이 세부적으로 구분했다. 여기서 생각해야 하는 점은 양수와 음수, 그리고 0과 1이다.

 

1. 양수의 경우 큰 수를 기준으로 정렬 했을 때 최댓값

2. 음수의 경우 작은 수를 기준으로 정렬시 최댓값

3. 1은 무조건 더할 때 큰 수를 만든다.

4. 0의 경우 마지막 남은 수와 묶어야 최댓값이 된다.(음수 배열에 넣어주면 됨)

 

이 규칙들과 내가 찾은 규칙들과의 차이점은 다음과 같다.

 

1. 양수와 음수를 따로 구분해 계산하는 것은 좋은 방향이었으나, 서로 정렬 방법이 달리해야 한다는 점을 알지 못함

2. 0의 경우 음수에 넣어야 최댓값을 출력 가능

 

이 두가지이다. 코드는 다음과 같다.

 

코드

import sys
input = sys.stdin.readline

T = int(input())
positive = []
negative = []
max_sum = 0

for _ in range(T):
  n = int(input())

  if n > 1:
    positive.append(n)
  elif n == 1:
    max_sum += 1
  else:
    negative.append(n)

positive.sort(reverse=True)
negative.sort()

if len(positive) % 2 == 0:
  # 양수가 짝수개일 경우에는 두개씩 곱해준다.
  for i in range(0,len(positive),2):
    max_sum += positive[i] * positive[i+1]
else:
  for i in range(0, len(positive)-1, 2):
    max_sum += positive[i] * positive[i+1]
  max_sum += positive[len(positive)-1]

if len(negative) % 2 == 0:
  # 음수가 짝수개일 경우에는 두개씩 곱해준다.
  for i in range(0,len(negative),2):
    max_sum += negative[i] * negative[i+1]
else:
  for i in range(0,len(negative)-1,2):
    max_sum += negative[i] * negative[i+1]
  max_sum += negative[len(negative)-1]

print(max_sum)

코드에서 또 아쉬웠던 점은 나는 입력값이 하나인 경우와 나머지를 조건문으로 구분하여 묶을 수를 구했지만, 위 코드에서는 for문을 좀 더 잘 활용했다. 

 

느낀 점

이번 문제를 풀면서 그래도 많이 발전했다는 것을 느꼈다. 문제를 읽자마자 어떤 식으로 풀어야 할지 감이 잡혔었고, 실제로 풀이 방향 또한 정답에 가까운 풀이였다. 완전히 스스로 풀지는 못했지만 처음 알고리즘을 접했을 때와 비교하면 많이 성장하였기에 뿌듯함이 있었던 문제였다. 앞으로도 이렇게 꾸준히 풀면서 감을 늘려나가야 되겠다.