[백준] 10819 : 차이를 최대로 / python

1️⃣ 문제 설명

10819번: 차이를 최대로

N개의 정수로 이루어진 배열 A가 주어진다.

이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 return

 

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

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

 

2️⃣ 풀이 전 계획과 생각

• 배열 A의 순서를 바꾸면서, 위의 식에 넣기
  • 배열 순서 → N! -> permutations(arr)
  • 위의 식 : 반복되는 패턴 찾아주자.
    • sum += abs(case[i] - case[i + 1])
• 위의 식의 결과를 힙이라는 자료구조에 넣기 (힙은 최대값과 최소값을 빠르게 찾는다.)
• 최댓값 출력하기

 

• 입력이 3 ≤ N ≤ 8이므로, 완전탐색 가능하다.

 

3️⃣ 풀이

from itertools import permutations
import heapq

N = int(input())
A = list(map(int, input().split()))
heap = []

cases = list(permutations(A))
answer = 0

for case in cases:
    sum = 0
    for i in range(N - 1):
        sum += abs(case[i] - case[i + 1])
    heapq.heappush(heap, (-sum, sum))

print(heap[0][1])

 

4️⃣ 다른 풀이

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

cases = list(permutations(A))
answer = 0

for case in cases:
    sum = 0
    for i in range(N - 1):
        sum += abs(case[i] - case[i + 1])
    answer = max(answer, sum)

print(answer)

 

5️⃣ 다른 풀이

N개의 정수로 이루어진 배열 A가 주어진다.

이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 return

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

⇒ M개 중에 N개를 뽑되, 순서가 있다.

K개 중 하나를 N번 선택하기 + 방문 처리

def recursive(current_picked):
    global answer

    if len(current_picked) == N:
        sum = 0
        for i in range(N - 1):
            sum += abs(current_picked[i] - current_picked[i + 1])
        answer = max(answer, sum)

    for i in range(N):
        if not visited[i]:
            visited[i] = 1
            current_picked.append(A[i])

            recursive(current_picked)

            visited[i] = 0
            current_picked.pop()

N = int(input())
A = list(map(int, input().split()))
visited = [0] * N

answer = 0
recursive([])
print(answer)

 

6️⃣ 풀이 후 알게된 개념과 소감

• 반복되는 패턴 찾아주자.