[ProblemSolving] 백준 1744번 수 묶기 문제풀이

백준 1744번 수 묶기 문제풀이에 대해서 알아보겠다. 문제 해설은 다음의 링크를 확인하면 된다. 문제 해설

1744번: 수 묶기

 

해당 문제는 그리드 유형의 문제로 최적을 방법을 고민해야 한다. 해당 문제를 해결하기 위해서는 3가지 조건을 충족하면서 계산을 해야 한다.

 

• 2 이상의 숫자는 오름차순 정렬하여 곱한다.
• 1은 더한다.
• 음수는 내림차순 정렬하여 곱한다.

위의 조건을 만족하기 위해서는 숫자를 입력받을 때 양의 정수, 1, 음의 정수를 따로 처리해줘야 한다. 다음의 조건을 만족하면서 코드를 작성하면 다음과 같다.

 

n = int(input())
 
answer = 0
positive = []
negative = []
 
for _ in range(n):
  num = int(input())
  if num == 1:
    answer += 1
  elif num > 1:
    positive.append(num)
  else:
    negative.append(num)
 
negative = sorted(negative, reverse=False)
positive = sorted(positive, reverse=True)
 
for i in range(0, len(negative), 2):
  if i+1 < len(negative):
    answer += negative[i] * negative[i+1]
  else:
    answer += negative[i]
 
for i in range(0, len(positive), 2):
  if i+1 < len(positive):
    answer += positive[i] * positive[i+1]
  else:
    answer += positive[i]
 
print(answer)

 

해당 문제는 양의 정수 중에 1은 곱하지 않아야 한다는 것과 음수는 내림차순, 양수는 오름차순으로 정렬해야 한다는 것이 중요했다.