인접한 원소의 곱의 합이 최대가 되도록 수열을 만드는 방법

16209번: 수열 섞기

 

수열 a1,a2,...,an이 주어질때 인접한 원소들의 곱 a1a2 + a2a3+... + an-1an이 최대가 되도록 수열을 섞고 싶다

 

그렇게 섞은 수열 하나만 구한다

 

-----------------------------------------------------------------------------------------------------------------------------------------------------------

 

적어도 양수는 양수끼리, 음수는 음수끼리 곱해야 한다는 것을 생각할 수 있다

 

또한 절댓값이 큰 것끼리 곱해야 커진다는 것도 생각할 수 있다

 

양수 그룹에서 큰 값들을 먼저 찾아서

 

a1 > a2 > .... > an이라고 한다면...

 

a1 a2를 먼저 배치하고 나서 a3을 어디다 넣어야할까?

 

a3 a1 a2로 a1 왼쪽에 넣는게 좋을 것

 

그 다음 작은 a4는 어디에? a2 오른쪽에 넣어야 조금이라도 더 커질것 a3 a1 a2 a4

 

그 다음 작은 a5는? a4 옆보다는 더 큰 a3 옆에 넣는게 좋을 것 a5 a3 a1 a2 a4

 

이런 식으로 큰수부터 왼쪽, 오른쪽 번갈아가며 배치하는 것이 유리하다

 

음수 그룹도 마찬가지로 음수는 절댓값이 큰 것끼리 곱해야하는데, 이는 (음수로) 작은 값끼리 곱해야 커지므로

 

음수로 작은 값끼리 왼쪽, 오른쪽 번갈아 배치하면 된다

 

왼쪽 오른쪽 번갈아 append하기에 적절한 deque를 사용

 

from collections import deque

n = int(input())

A = list(map(int,input().split()))

minus = []
plus = []

for i in range(n):
    
    if A[i] <= 0:
        
        minus.append(A[i])
    
    else:
        
        plus.append(A[i])

B = deque([])
C = deque([])

minus.sort()
plus.sort()

if len(plus) >= 1:

    B.append(plus[-1])
    f = False

    for i in range(len(plus)-2,-1,-1):

        if f == False:

            B.append(plus[i])
            f = True
        
        else:
            
            B.appendleft(plus[i])
            f = False

if len(minus) >= 1:

    C.append(minus[0])
    f = False

    for i in range(1,len(minus)):
        
        if f == False:
            
            C.append(minus[i])
            f = True

        else:
            
            C.appendleft(minus[i])
            f = False

 

 

이제 마지막으로 음수부분과 양수부분을 합쳐야하는데

 

당연히 서로 옆에 붙여서 음수 * 양수가 1번만 되게 일어나는게 유리할 것

 

근데 어떻게 붙여야하지?

 

양수 그룹의 왼쪽, 오른쪽

 

음수 그룹의 왼쪽, 오른쪽 값은 O(1)에 접근할 수 있으니 각각 양수 왼 * 음수 왼, 양수 왼 * 음수 오

 

양수 오 * 음수 왼, 양수 오 * 음수 오 4가지에 대해서 비교해서

 

4가지가 더 작은 값을 기준으로 붙이면 될 것

 

B = [B[0],B[1],...,B[-1]]

 

C = [C[0],C[1],...,C[-1]]

 

B[0] * C[0]가 제일 작으면?

 

C[-1],...,C[1], C[0] , B[0],B[1],...,B[-1]로 붙이면 될거고

 

B[0]*C[-1]이 제일 작으면?

 

C[0],C[1],...,C[-1] B[0],B[1],...,B[-1]로 붙이면 될거고

 

B[-1]*C[0]가 제일 작으면?

 

B[0],B[1],...,B[-1],C[0],C[1],...,C[-1]로 붙이면 될거고

 

B[-1]*C[-1]이 제일 작으면?

 

B[0],B[1],...,B[-1],C[-1],C[-2],...,C[1],C[0]로 붙이면 될거

 

if len(B) >= 1 and len(C) >= 1:

    x1 = B[0]*C[0]
    x2 = B[0]*C[-1]
    x3 = B[-1]*C[0]
    x4 = B[-1]*C[-1]

    D = [x1,x2,x3,x4]
    D.sort()

    if D[-1] == x1:
        
        while C:
            
            c = C.popleft()
            B.appendleft(c)

    elif D[-1] == x2:
        
        while C:
            
            c = C.pop()
            B.appendleft(c)

    elif D[-1] == x3:
        
        while C:
            
            c = C.popleft()
            B.append(c)

    else:
        
        while C:
            
            c = C.pop()
            B.append(c)

if len(B) >= 1:

    print(*B)

elif len(C) >= 1:
    
    print(*C)