백준 10819번 - 차이를 최대로

차이를 최대로 문제 바로 가기

풀이 날짜: 2026-03-01

baekjoon 알고리즘 문제 풀이

풀이 코드


n = int(input())
num = list(map(int, input().split()))

used = [False] * n
store = []
best = 0

def dfs(depth):
    global best

    if depth == n:
        current_score = 0
        for i in range(n-1):
            current_score += abs(store[i] - store[i+1])
        best = max(best, current_score)

    for i in range(n):
        if not used[i]:
            used[i] = True
            store.append(num[i])

            dfs(depth+1)

            store.pop()
            used[i] = False

dfs(0)
print(best)

문제 핵심 정리

이 문제는 주어진 숫자들을 한 줄로 재배치하여, 인접한 두 수의 차이의 절댓값을 모두 더한 값이 최대가 되도록 하는 순서를 찾는 문제다. 즉, 단순히 숫자를 정렬하는 문제가 아니라, 가능한 모든 순열을 고려하여 각 순열에 대해 값을 계산하고 그 중 최댓값을 구해야 한다. 핵심은 “어떤 순서로 배열하느냐”에 따라 결과 값이 달라진다는 점이다.

문제 접근: 모든 순열 탐색

문제 조건상 N ≤ 8이므로, 최악의 경우 8! = 40320가지의 순열을 탐색하면 된다. 이는 완전탐색(브루트포스)이 가능한 범위다. 따라서 백트래킹을 이용하여 모든 순열을 직접 생성하고, 완성된 순열마다 값을 계산하는 방식으로 접근하였다.

상태 설계: used와 store

백트래킹을 구현하기 위해 두 가지 배열을 사용했다.

uesd: 특정 숫자가 이미 선택되었는지를 표시해 중복 사용을 방지한다.
store: 현재까지 선택된 숫자들을 순서대로 저장하여 하나의 순열을 구성하는 역할을 했다. 즉, store는 현재 만들어지고 있는 순열이고, uesd는 해당 숫자의 사용 여부를 관리한다.

depth의 의미

depth는 현재까지 선택한 숫자의 개수를 의미한다. depth == n이 되면 하나의 순열이 완성된 상태이므로, 그때 인접한 원소들의 차이를 계산한다.

백트래킹의 핵심 구조

선택 → 재귀 호출 → 상태 복구

한 숫자를 선택하고, 그 선택을 기반으로 다음 단계로 내려간 뒤, 해당 경우의 탐색이 끝나면 반드시 원래 상태로 되돌려야 다음 경우를 탐색할 수 있다.

내가 헷갈렸던 부분

처음에는 왜 store.pop()과 used[i] = False가 필요한지 이해하지 못했다. 하지만 재귀 호출이 끝난 뒤에는 다른 선택을 시도해야 하므로, 이전 선택을 반드시 되돌려야 한다는 것을 깨달았다.

또한, range(n - 1)로 반복하는 이유도 인덱스 범위를 벗어나지 않기 위함이라는 점을 다시 한 번 정리하게 되었다.

느낀 점

이 문제를 통해 “모든 순열을 만드는 것”과 “백트래킹으로 상태를 관리하는 것”의 차이를 명확히 구분할 수 있었다. 특히 전역 변수(best)를 사용하여 최댓값을 갱신하는 구조와, 상태 복구의 중요성을 다시 한 번 체감했다.

Vienna sausage