[백준] 10819번: 차이를 최대로

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

initial

visual explanation good
https://kill-xxx.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-10819%EB%B2%88-%EC%B0%A8%EC%9D%B4%EB%A5%BC-%EC%B5%9C%EB%8C%80%EB%A1%9C-%EB%B8%8C%EB%A3%A8%ED%8A%B8%ED%8F%AC%EC%8A%A4-%EA%B7%B8%EB%A6%BC-%ED%92%80%EC%9D%B4

I first spent a long time how to implement this backtracking cuz I was solving backtracking questions yesterday and they all placed useful parameters like (day,late,absent) or (total,depth,plus,minus,multi,divi) to check validity of condition whether or not to exit out of the recursion. But that is when we can see we have a choice - like being late/absent/late or doing plus/minus/multi/div. But here our choice is fixed - add an element in the list or not. So I overthought the impl too much and reminded me that you have to adjust your approach. It is not always placing useful parameters in backtracking.

Here I placed an empty list and added the elements until its length is n. Then I calculated the sum by abs(lst[i]+lst[i-1) and in a for loop until n-1 (not n cuz u will get list index out of range error). I tried implementing this calculation in my backtracking function parameter but after thinking a lot, I still couldnt. So as I’ve said, unless you have a range of choices, it might be more optimal to check validity of condition outside.

revisited jan 16th 2024

yes it is like that n+m backtracking question. For any dfs or backtracking, we first think of the recursion end condition. So when our length is n, we calc the max answer and return cuz we dont wanna traverse the main logic once our length of list is n.

We need a visited list and list to append incoming element and mark it as visited. Our visited list will help us guide the next elements to be added. Once we reach the end condition, we have to backtrack by marking it as unvisited and popping from our list via pop().

revisited june 14th

i thought of placing parameters in dfs to calculate the sum along the way but the initial approach is cleaner

revisted june 25th

i again couldnt solve as i tried placing parameters like dfs(boolean_check, total_sum, tmp) but the intial approach is much more simple.

solution

n = int(input())
lst = list(map(int, input().split()))
ans = 0
visited = [False for _ in range(n)]

def dfs(tmp):
    global ans
    if len(tmp) == n:
        hola = 0
        for i in range(n - 1):
            hola += abs(tmp[i] - tmp[i + 1])
        ans = max(ans, hola)
        return

    for i in range(n):
        if not visited[i]:
            tmp.append(lst[i])
            visited[i] = True
            dfs(tmp)
            visited[i] = False
            tmp.pop()

dfs([])
print(ans)

complexity

we are generating all poss of permutations so it is o(n!) while space is n