BOJ 백준 10819: 차이를 최대로

Table of contents

들어가며

이 문제는 완전 탐색 문제입니다.
N이 최대 8밖에 되지 않기 때문에, 모든 경우의 수를 따져 보면 됩니다.
이때 시간 복잡도가 $O(N!N)$이고, 문제에서 순열을 구해야 합니다. (근데 N이 최대 8이면 사실 일차항 N은 무시해도 되지 않나 싶네요…)

풀이 과정

순열을 만들어서 돌리면서, 각 경우의 수마다 요소들의 차의 합을 계산해서 비교하면 됩니다.
이때, list A의 Permutation을 구할 때, permutation library를 써도 되지만, 백트래킹 기법을 이용하여 한 번 구해 봤습니다.

AC 받은 Python 코드

import sys

# sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def calculate():
    ret = 0
    for i in range(N - 1):
        ret += abs(permutatedA[i] - permutatedA[i + 1])
    return ret


def permutation(cur_len):
    # base condition 1
    if cur_len == N:
        global ans
        ans = max(ans, calculate())
        return

    for next_idx in range(N):
        if isUsed[next_idx]:
            continue
        isUsed[next_idx] = True
        permutatedA.append(A[next_idx])
        permutation(cur_len + 1)
        isUsed[next_idx] = False
        permutatedA.pop()


if __name__ == "__main__":
    N = int(input().rstrip())
    A = [*map(int, input().rstrip().split())]
    permutatedA = []
    isUsed = [False for _ in range(N)]
    ans = -1
    for i in range(N):
        isUsed[i] = True
        permutatedA.append(A[i])
        permutation(1)
        isUsed[i] = False
        permutatedA.pop()
    print(ans)