[백준 10819] 차이를 최대로

1. 문제

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

10819번: 차이를 최대로

2. 접근 방법

주어지는 숫자의 갯수가 2~8이라 순열을 사용해도 되겠다 싶었습니다.

 

1. 순열을 만들기 전에 미리 요소 하나를 담고

2. 여기에 요소 하나를 추가할 때마다 기존 순열 리스트에 담겨있는 맨 마지막 숫자와의 차이를 변수에 담아줍니다.

3. 순열 리스트의 요소 갯수가 N개가 되었을 때, 숫자들의 차이를 합친 변수의 크기가 기존 최댓값보다 클 경우 갱신해줍니다.

3. 코드

python

def perm(k, temp):
    global N, inputs, answer, max_val

    if k == N:
        if temp > max_val:
            max_val = temp
        return
    
    for i in range(N):
        if not visited[i]:
            visited[i] = True
            diff = abs(answer[-1]-inputs[i])
            temp += diff
            answer.append(inputs[i])
            perm(k+1, temp)
            visited[i] = False
            temp -= diff
            answer.pop()

N = int(input())
inputs = list(map(int, input().split()))
max_val = 0

for i in range(N):
    visited = [False]*N
    answer = [inputs[i]]
    visited[i] = True
    perm(1, 0)

print(max_val)

4. 마치며

마치며~!