[백준] 10819번: 차이를 최대로 - 파이썬/python

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

10819번: 차이를 최대로

접근 방식

- 주어진 숫자들의 모든 배열 경우의 수 탐색 방법 (개별 숫자 단위, 전체 배열 단위 등)

 

코드 풀이

from itertools import permutations

n = int(input())
nums = list(map(int, input().split()))
ans = []

for nums_per in permutations(nums):
    sums = 0
    for i in range(n-1): # 0, 1, 2 .. n-2
        sums += abs(list(nums_per)[i] - list(nums_per)[i+1]) # 두 개씩 차이의 합을 누적합      
    ans.append(sums) # 하나의 배열에서 나온 차이합 결과를 ans 리스트에 저장
    
print(max(ans)) # 저장한 값을 중 최댓값

처음에는 직관적인 방법으로 접근하여, 가장 큰 수와 가장 작은 수를 번갈아가며 나열하는 조합에서 차이 합의 값이 최대가 나올 것이라고 생각했습니다. 하지만 테스트케이스에서조차 오답이 나왔기 때문에 위의 방법처럼 nums 리스트의 순열을 for loop로 만들어, 그 안에서 인덱스 접근을 통해 차이값을 더해주는 방법으로 코드를 작성하였습니다.

 

오답 이유

코드를 작성하는 과정에서, 숫자를 두 개씩 짝을 짓는 모든 경우의 수를 조사하여 각각의 차이의 합을 구하려고 했습니다. 따라서 재귀 함수를 작성하려고 했지만, 두 개씩 짝을 지을 필요 없이 인접한 모든 수의 차이의 합을 구하는 문제였습니다.

간단하게 작성할 수 있는 풀이이지만, 재귀 함수 쪽으로 생각하게 됨에 따라 시간이 오래 소요됐던 문제입니다. (재귀 함수의 경우 2개씩 원소를 제거하며 원소의 갯수가 0이 될 때까지 재귀함수로 들어가게 됩니다. 한번 끝까지 들어가면 하나의 경우의 수에서의 정답값이 나오지만, 재귀함수는 다시 나오게 되는 과정이 있으므로 원본 배열에서 숫자를 이미 제거했다면 이에 대한 고민이 필요하기 때문입니다.)