[백준] 10819 파이썬(python) : 차이를 최대로

10819번 : 차이를 최대로

 

 

백트래킹을 이용한 풀이)

import sys
n = int(sys.stdin.readline())
number = list(map(int, sys.stdin.readline().split()))
temp, res = [], [] #1

def backTracking(depth):
    if depth == n: #2
        t = 0
        for i in range(n-1): #3
            t += abs(number[temp[i+1]] - number[temp[i]])
        res.append(t)
        return
    for i in range(n):
        if i not in temp: #4
            temp.append(i)
            backTracking(depth+1) #5
            temp.pop()

backTracking(0)
print(max(res))

 

#1 : 인덱스를 넣어줄 임시리스트와 결과값을 출력할 리스트

#2 : 백트래킹의 깊이가 n이 될때

#3 : 문제의 조건식 실행후 res에 삽입

#4 : 없는 값들만 리스트에 삽입하여 완전탐색

#5 : 깊이를 높혀가며 재귀호출

 

순열을 이용한 풀이)

import sys
from itertools import permutations
n = int(sys.stdin.readline())
number = list(map(int, sys.stdin.readline().split()))
res = [] #1
for nums in permutations(number, n): #2
    t = 0
    for i in range(n-1): #3
        t += abs(nums[i+1]-nums[i])
    res.append(t)
print(max(res)) #4

 

#1 : 결과를 출력할 리스트

#2 : number리스트에서 n개의 숫자를 꺼내 순서를 고려하는 순열을 nums라는 변수로 뽑는다.

#3 : n-1까지 인덱스를 반복하여 문제에서 주어진 조건식을 실행 후 res리스트에 삽입

#4 : res리스트에서 가장 큰 값을 출력

 

아래는 백트래킹, 위는 순열

 

---

백트래킹, 브루트포스 문제는 순열과 조합을 이용할 수 있을지 생각해보도록 하자.