10819

날짜 : 2023. 03. 06

사용 언어 : python

 

문제

 

 

코드

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
res = 0
temp = []


def back(cur):
    if cur == n:
        t = 0
        for i in range(n-1):
            t += abs(a[temp[i]]-a[temp[i+1]])
        global res
        #print(temp, t)
        res = max(res, t)  # 결과값 갱신
        return
    for i in range(n):
        if i not in temp:  # 해당 수가 배열에 없다면
            temp.append(i)  # 추가(백트래킹)
            back(cur + 1)  # 재귀
            temp.pop()  # 삭제
    return


back(0)
print(res)

 

 

풀이

- 백트래킹을 활용하여 temp라는 임시배열을 통해 해당 수열을 구하고 그 수열에 따라 결과값을 도출해 이를 최신화하는 문제이다.

- n의 값(전체 배열의 크기)이 크지 않았기 때문에(3 <= n <= 8) 브루트포스 방식으로 풀이가 가능했다.

 

 

알게된 점

- 아직 백트래킹을 자유자재로 풀이에 사용하기에는 조금 부족한 것 같다.

- 브루트포스는 트리 형태로 그려가면서 문제를 푸는 방식으로 연습해야겠다.

 

 

참고 사이트

-