📗문제 설명

문제 바로 가기

❓ N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

• 입력
  • 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.
• 출력
  • 첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.
• 예시

  6
  20 1 15 8 4 10
  
  62
  
  # 반례 
  # 입력
  5
  -66 -86 51 -87 -27
  # 출력
  374
  
  '''
  case1
  input
  6
  2 -4 -4 0 1 4 
  output
  29
  
  case 2
  input
  4
  -1 -5 2 1 
  output
  16
  
  '''

💡문제 풀이 IDEA

• deque써서 큰거 작은거 큰거 작은거 순으로 배치하면 최댓값이 나오지 않을까?
  • 대신 마지막 수는 맨 앞으로 보내서 가장 큰값과 비교해서 차이를 만든다.

1. 1차 코드 → 무조건 맨 앞이 가장 작은 수가 오게 했다.
   1. 하지만 가장 큰 차이를 만들때 마지막에 오는 값이 제일 큰값과 차이가 더 큰지, 제일 작은값과 차이가 더 큰지를 비교해야한다.
2. 2차 코드 → 맨앞에 오는 숫자를 가장 작은수가 오는 케이스, 가장 큰수가 오는 수로 나누어 분류하였다.
   1. 그중 더 큰 값을 답으로 출력하게 하였다.

👨🏻‍💻문제 풀이 CODE

from collections import deque
import sys

input=sys.stdin.readline

N=int(input())
arr=sorted(map(int,input().split()))

print(arr)
arr=deque(arr)
arr2=deque()
while arr!=deque():
    if len(arr)==1: # 1개남았을때 
        arr2.appendleft(arr.pop())
    else: # 2개 남았을 때 
        arr2.append(arr.popleft())
        if arr==[]:
            break
        elif len(arr)==1:
            arr2.appendleft(arr.pop())
        else:
            arr2.append(arr.pop())
print(arr2)
answer=0
for i in range(len(arr2)-1):
    answer+=abs(arr2[i]-arr2[i+1])

print(answer)

from collections import deque
import sys
input=sys.stdin.readline

def main():
    N=int(input())
    arr=sorted(map(int,input().split()))
    # case를 2개로 나누자. 
    case=[]
    case.append(case1(arr))
    case.append(case2(arr))
    print(max(case))

# case 1 작은게 먼저 올때 
def case1(arr):
    arr=deque(arr)
    arr2=deque()
    while arr!=deque():
        if len(arr)==1: # 1개남았을때 
            arr2.appendleft(arr.pop())
        else: # 2개 남았을 때 
            arr2.append(arr.pop())
            if arr==[]:
                break
            elif len(arr)==1:
                arr2.appendleft(arr.pop())
            else:
                arr2.append(arr.popleft())
    answer=0
    for i in range(len(arr2)-1):
        answer+=abs(arr2[i]-arr2[i+1])
    return answer

# 큰게 먼저 올때 
def case2(arr):
    arr=deque(arr)
    arr2=deque()
    while arr!=deque():
        if len(arr)==1: # 1개남았을때 
            arr2.appendleft(arr.pop())
        else: # 2개 남았을 때 
            arr2.append(arr.popleft())
            if arr==[]:
                break
            elif len(arr)==1:
                arr2.appendleft(arr.pop())
            else:
                arr2.append(arr.pop())
    answer=0
    for i in range(len(arr2)-1):
        answer+=abs(arr2[i]-arr2[i+1])
    return (answer)

if __name__=="__main__":
    main()