백준 / 차이를 최대로 / 10819번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 차이를 최대로 / 10819번 (실버 2단계)

문제 사이트: https://www.acmicpc.net/problem/10819

 

문제 설명

---

나의 풀이

answer = 0


def calculate_expression(arr):
    total = 0
    for i in range(len(arr) - 1):
        total += abs(arr[i] - arr[i + 1])
    return total


def solution(arr, n):
    visited = [False] * n

    def dfs(path):
        global answer
        if len(path) == n:
            answer = max(answer, calculate_expression(path))
            return

        for i in range(n):
            if not visited[i]:
                visited[i] = True
                dfs(path + [arr[i]])
                visited[i] = False

    dfs([])

    
def main():
    global answer

    n = int(input())
    arr = list(map(int, input().split()))

    solution(arr, n)

    print(answer)


if __name__=="__main__":
    main()

---

※ 알아야 할 것

코드 설명

dfs(path + [arr[i]])	원래 path는 그대로, 새 리스트 생성해서 넘김
path.append(arr[i]); dfs(path); path.pop()	같은 리스트를 공유하므로 수동 복원이 필요함

위 코드에서 append, pop를 사용하지 않고 path + [arr[i]]를 사용한 이유는 복원할때 수동으로 복원해야하기 때문에 했습니다.

위 path + [arr[i]] 방식은 path는 새로운 배열을 생성하므로 깊은 복사의 과정이 발생합니다. 하지만 append(), pop()은 하나의 배열을 가지고 사용하기때문에 복원하는 과정에서 어렵습니다.