[BOJ] 10819. 차이를 최대로

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

10819번: 차이를 최대로

 

 

1. 해결방법

"""
1. 아이디어
- 배열안 2개의 원소 값 차이의 합 중 최대 값을 구하는 문제.
- 하나의 원소를 먼저 선택하고, n-1개 중 추가적으로 계속 뽑는 형식.
- n-1, n-2 ... 재귀적으로 들어가면서 차이 값을 구한다.

2. 시간복잡도
- O(2^n)

3. 자료구조
- 백트래킹 : 재귀
"""

 

 

2. 정답코드

입력 예제(1)

6
20 1 15 8 4 10

출력 예제(1)

62

 

코드

import sys
input = sys.stdin.readline


N = int(input())
A = list(map(int, input().split()))
chk = [False for _ in range(N)]
answer = []
max_v = 0


# recur
def recur(depth):
    global max_v

    # 재귀 종료 지점
    if depth == N:
        temp = 0
        for j in range(N - 1):
            temp += abs(answer[j] - answer[j + 1])
        max_v = max(max_v, temp)
        return

    # 재귀
    for i in range(N):
        if chk[i] == False:
            answer.append(A[i])
            chk[i] = True
            recur(depth + 1)
            chk[i] = False
            answer.pop()



# main
recur(0)
print(max_v)