[백준 / Python] 차이를 최대로_10819

https://www.acmicpc.net/problem/10819

정답 코드

n = int(input()) check = [False for _ in range(n)] orders = [0 for _ in range(n)] data = list(map(int, input().split())) result = [] def dfs(idx): if idx == n: result.append(cal_solution()) return for i in range(n): if not check[i]: orders[idx] = i check[i] = True dfs(idx + 1) check[i] = False def cal_solution(): sum = 0 for i in range(n - 1): sum += abs(data[orders[i]] - data[orders[i + 1]]) return sum dfs(0) print(max(result)) 

문제 해설
이 문제는 주어진 값들을 뽑는 순서를 구하는 문제와 같다.
문제 예시를 가지고 설명하자면, 20 1 15 8 4 10를 뽑는 순서를 구하는 것이다.
수학적으로는 그냥 수열(Permutation)을 구하는 것이다.

이것을 그림으로 표현하면 다음과 같고,, 이를 재귀함수로 풀어낸 코드이다.

그래도 좀 헷갈린다. 그럼 이 부분을 차근차근 보면 된다.
각각의 의미를 보자.
idx는 정답으로 도출될 배열의 순서를 의미한다. 즉, idx = 1인 상황에서는 첫 번째 칸에 어떤 수가 올지를 결정하는 부분이다.
idx에 대하여 반복문을 통해 해당 순서에 들어갈 노드를 모든 경우의 수를 고려하여 넣는 것이다.



앞으로 재귀를 헷갈리는 일이 생기면, 이 문제를 다시 돌아보도록 하자.
다른 어려운 문제보다 개념의 핵심을 잘 짚어낸 가성비 좋은 문제들이 있다.
이 문제는 재귀개념에 있어서 가성비가 좋은 문제이다.