백준: 10819 차이를 최대로

문제

10819번: 차이를 최대로

 

문제 풀이

 앞의 10974 모든 순열에서 특정 수가 주어지는 경우로 변경된 문제이다. 이 역시 DFS를 통해 순열을 구하는 법을 알고 있다면 쉽게 풀 수 있다. 입력되는 값들은 정렬된 상태가 아니므로, DFS를 통해 경우의 수를 구하기 전에 정렬이 필요하다.

 

코드

DFS를 사용한 문제 풀이

from sys import stdin


def dfs(depth):
    global answer

    if depth == n:
        answer.append([nums[i] for i in check])
    else:
        for i in range(n):
            if i in check:
                continue
            check[depth] = i
            dfs(depth + 1)
            check[depth] = -1

if __name__ == '__main__':
    answer = []
    n = int(stdin.readline())
    nums = sorted(list(map(int, stdin.readline().split())))
    check = [-1] * n
    dfs(0)
    min_case = 0
    for case in answer:
        sum_case = 0
        for i in range(n - 1):
            sum_case += abs(case[i] - case[i + 1])
        min_case = max(min_case, sum_case)
    print(min_case)

 

itertools를 활용한 문제 풀이

from itertools import permutations
N = int(input())
cases = permutations(sorted(list(map(int, input().split()))))
answer = 0

for case in cases:
    sum_case = 0
    for i in range(N - 1):
        sum_case += abs(case[i]-case[i + 1])
    answer = max(answer, sum_case)
print(answer)