차이를 최대로 - 10819번

문제

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

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

입력
첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력
첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

풀이

다음의 코드는 정답이다.

순열

import sys
from itertools import permutations
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
perms = []
for p in permutations(A, N):
    perms.append(p)

currMax = -1e999
tmp = 0

for p in perms:
    tmp = 0
    for i in range(N-1):
        tmp += abs(p[i] - p[i+1])
    if tmp > currMax:
        currMax = tmp

print(currMax)

완전탐색(재귀)

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
currMax = -1e999
visited = [0]*N
arr = []
sum = 0

def dfs(depth):
    global sum, currMax
    if depth==N:
        for i in range(N-1):
            sum += abs(arr[i]-arr[i+1])
        if sum>currMax:
            currMax = sum
        sum = 0
        return
    for i in range(N):
        if visited[i]==0:
            arr.append(A[i])
            visited[i] = 1
            dfs(depth+1)
            arr.pop()
            visited[i] = 0
dfs(0)
print(currMax)

지난 번 문제풀이 때 itertools 라이브러리의 순열로 풀 수 있는 문제는 고대로 재귀로 순열을 만들어서 푸는 식으로 접근했었던 기억이 있는데 이번엔 그렇게 하지 않았다.

카드놓기 문제(https://velog.io/@hbtopkr/%EC%B9%B4%EB%93%9C-%EB%86%93%EA%B8%B0-%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98-%EC%9E%85%EB%AC%B8%EC%9D%84-%EC%9C%84%ED%95%9C-%EC%88%9C%EC%B0%A8%EC%A0%81-%EB%94%94%EB%B2%84%EA%B9%85)를 열심히 들여다 보았었는데, 이런 식으로 방문 혹은 활용의 체크를 표시를 표시했다가 지웠다가 하는 기법으로 탐색하는 문제가 많은 것 같다. 이 문제 역시 같은 접근이라 이해가 바로 됐다.

아래 for문에서가 아니라 탈출용 if문 안에서 sum을 만들어 currMax와 비교대조하는 등의 많은 수행을 하도록 적은 점이 내겐 새로웠다.