백준 1744번. 수 묶기

💡문제 분석 요약

<문제 분석>

• 길이가 N인 수열의 합을 구하려고 한다. 근데 그 숫자를 모두 더해서 구하는게 아니에요 !
• 수열의 두 수를 묶으려고 해요.
  • 위치에 상관없이 묶을 수 있어요
  • 자기 자신과 자기 자신을 묶을 수는 없어요
  • 어떤 수를 묶게 되면 수열의 합을 구할 때 묶은 수는 서로 곱한 다음에 더해지게 되어요
• 수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야 해요.
  • 안 묶어도 되고,
  • 묶으려면 1번만 묶을 수 있고
• 각 수를 적절히 묶어서 그 수열의 합이 최대가 되게 하는 프로그램을 짜세요
• 수열에 있는 숫자는 -1000 ≤ ≤ 1000 이다.
  • 즉, 음수가 있다는 것 ! 0이 있다는 것 !
• 결과 값은 항상 2^31보다 작다.

<아이디어>

• 자 합이 최대가 나오려고 합니다.
  • ⇒ 그리디의 냄새가 납니다 ~ 항상 최고를 만들어야 하니까요 ?
• 수의 종류는 음수, 0, 양수이다.
• 자 어떻게 항상 최고를 만들까요 ?
  • 1 초과 양수
    • 1 초과 양수를 보는 이유는 1*3 = 3 < 1+3 = 4 같은 경우 때문이다. 1은 곱했을 때 더 큰 합을 만드는데 도움이 되지 않기 때문에 1만 따로 모아서 결과 수열에 넣어주는게 큰 합을 만드는데 도움이 된다. ⭐⭐⭐⭐⭐ (1의 속성)
    • 양수는 가장 큰것들 2개씩 묶어서 곱하면 항상 최고가 되는데 도움이 되고
    • 양수가 1개 남았으면 그냥 결과 수열에 더하면 되고
  • 음수
    • 음수인 것들은 가장 작은 2개씩 묶어서 곱하면 양수가 되어서 → 항상 최고가 되는데 도움이 되고
    • 혹시 음수 하나가 남았고 0이 있다면
      • 그 둘은 곱해주는 것이 좋고
    • 음수 하나가 남았는데 0이 없다면
      • 그냥 결과 수열에 더해줘야 하고
  • 0
    • 합을 만드는 것에 영향을 미치지 않기에 굳이 결과 수열에 넣어줄 필요 없고
  • 1
    • 1들을 모두 결과 수열에 넣어주기
  • 결과 수열을 sum 한 것이 정답 !
• 핵심은 음수 / 0 / 1 / 양수 이렇게 분리해서 처리해주는 것
  • 앞 뒤에서 자유롭게 뽑기 위해 음수, 양수는 deque로 만든다. 0과 1은 상관 없음
  • 수열의 숫자를 받아서 각 배열에 넣기
    • if num<0: neg.append(num)
      elif num==0: zero.append(num)
      elif num>1: pos.append(num)
      elif num==1: one.append(num)
  • 음수
    • while neg의 길이가 1보다 클 때 까지
      pop, pop → 곱하기 → new_arr.append(묶은 수)
    • neg가 남아 있다면(
      • 만약 if zero라면
        new_arr.append(남아있는 마지막 하나를 뽑아요 neg.pop() * zero.pop())
      • else라면
        new_arr.append(neg.pop())
  • 1초과 양수
    • while pos의 길이가 1보다 클 때 까지
      pop, pop → 곱하기 → new_arr.append(묶은 수)
    • pos가 남아 있다면 (1개 남아있는거죠)
      • new_arr.append(남아있는 마지막 하나를 뽑아요 배열.pop())
  • 1
    • while one: res_arr.append(one.pop())
  • print(sum(res_arr))

1 ≤ N < 50

-1000 ≤ 각 수열의 수 ≤ 1000

시간 제한 : 2초

엣지 케이스

• 놓쳤던 테스트 케이스

    1 + 1 = 2
  
    2
    1
    1
    ans = 2

  ⇒ 1의 속성을 생각하게 된다.
• -1 + 1 + 2 = 2 3 -1 1 2 ans = 2

입출력

• 입력
• 4 -1 2 1 3
• 출력
• 6 # 합이 최대가 나오게 했을 때의 수열의 합 (항상 2^31보다 작다, 음수일 수도 있다.)

💡알고리즘 설계 (수도 코드)

• 앞 뒤에서 자유롭게 뽑기 위해 음수, 양수는 deque로 만든다. 0과 1은 상관 없음

1. 수열의 숫자를 받아서 각 배열에 넣기
   • if num<0: neg.append(num)
     elif num==0: zero.append(num)
     elif num>1: pos.append(num)
     elif num==1: one.append(num)
2. 음수
   • while neg의 길이가 1보다 클 때 까지
     pop, pop → 곱하기 → new_arr.append(묶은 수)
   • neg가 남아 있다면(
     • 만약 if zero라면
       new_arr.append(남아있는 마지막 하나를 뽑아요 neg.pop() * zero.pop())
     • else라면
       new_arr.append(neg.pop())
3. 1초과 양수
   • while pos의 길이가 1보다 클 때 까지
     pop, pop → 곱하기 → new_arr.append(묶은 수)
   • pos가 남아 있다면 (1개 남아있는거죠)
     • new_arr.append(남아있는 마지막 하나를 뽑아요 배열.pop())
4. 1
   • while one: res_arr.append(one.pop())
5. print(sum(res_arr))

💡코드

34088 KB	64 ms

import sys
from collections import deque

n = int(sys.stdin.readline().strip())
neg = deque()
pos = deque()
zero = []
one = []
res_arr = []

for _ in range(n): # O(n)
    num = int(sys.stdin.readline().strip())
    if num<0: neg.append(num)
    elif num==0: zero.append(num)
    elif num>1: pos.append(num)
    elif num==1: one.append(num)

neg = deque(sorted(neg)) # O(nlogn)
while len(neg)>1: # O(n)
    res_arr.append(neg.popleft()*neg.popleft())
if neg: # neg가 1개 남아있음
    if zero: # 0이 있다면, 0이랑 곱해서 무효화시키기
        res_arr.append(neg.popleft()*zero.pop()) # neg.popleft()
    else:
        res_arr.append(neg.popleft())

pos = deque(sorted(pos, reverse=True)) # O(nlogn)
while len(pos)>1: # O(n)
    res_arr.append(pos.popleft()*pos.popleft())
if pos:
    res_arr.append(pos.popleft())

while one: # O(n)
    res_arr.append(one.pop())

print(sum(res_arr)) # O(n)

💡시간 복잡도

O(5n + 2nlogn) = O(nlogn)

⇒ $O(50log50) < 2*10^6$

💡 틀린 이유

• 1에 대한 속성을 고려하지 않고 음수 / 0 / 양수 에 대해서만 생각함
• 3 -1 1 2 ans = 1이 나왔음 왜냐하면 1의 속성을 고려하지 않고 양수 범위에 포함해서 2*1 + -1 연산이 되었기 때문에 !

💡 틀린 부분 수정 or 다른 풀이

• 1에 대한 ‘합, 곱’ 속성을 고려해서 1을 따로 분리하여 res_arr에 전부 더하기 !

elif num==1: one.append(num)

while one: # O(n)
    res_arr.append(one.pop())

💡 느낀점 or 기억할 정보

• print(sum([])) = 0
• 1은 다른 양수(k)랑 곱했을 때 k 본인이 되게 만들기 때문에 무조건 1*k < 1+k 이다.