[백준] 16198번: 에너지 모으기

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

initial

This approach would be correct if the question asked not to pop that element once visited. But we need to pop it so that when we do lst[i+1] we dont meet the last element that we just visited.

for example, 1 2 3 4 and we are at 2, we go to 3 at next iteration. But since 2 is still in our list, we add 24 to our accumulated sum, which is wrong. We need to add 14 cuz 2 needs to be disregarded. So how do we pop it??

1)

            k = a[i]
            del a[i]

very careful that del k doesnt work. k is just a variable that holds a reference to an element in list. It thus doesnt affect the list in any way.

2)

v = w.pop(i)

wrong approach where I didnt make the pop

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

hola = 0

def dfs(ans):
    global hola
    if all(visited):
        hola = max(hola,ans)
        return

    for i in range(n):
        if i!=0 and i<n-1:
            if not visited[i]:
                ans+=lst[i-1]*lst[i+1]
                visited[i]=True
                dfs(ans)
                ans-=lst[i-1]*lst[i+1]
                visited[i]=False
dfs(0)
print(hola)

solution

why is this wrong?

for i in range(len(lst)):
if i!=0 and i<n-1:
main logic

when this is correct?

for i in range(1, len(lst)-1):

That is cuz when we have [1,2,4], where 3 is popped, when i=2, k=4. Since we are at the end of the list, we should stop but my condition allows it. (tbc)

correct where we popped the visited element using del:

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

hola = 0

def dfs(ans):
    global hola
    if len(lst)==2:
        hola = max(hola,ans)
        return

    for i in range(1, len(lst)-1):
        k = lst[i]
        ans+=lst[i-1]*lst[i+1]
        del lst[i]
        dfs(ans)
        lst.insert(i,k)
        ans-=lst[i-1]*lst[i+1]
dfs(0)
print(hola)

complexity

The time complexity of your code can be analyzed as follows:

1. The function dfs is called recursively, and for each call, it performs some operations on the lst list and computes ans.

2. The dfs function is called at most 2 * (n - 2) times, where "n" is the length of the lst list. This is because you are looping from index 1 to n-2 (skipping the first and last elements), and for each position, you call dfs twice: once after deleting the element at index i, and once after inserting it back.

3. For each call of dfs, you are performing some list operations (deletion and insertion), which takes O(n) time in the worst case.

Therefore, the overall time complexity of your code is O(n 2 (n - 2)) = O(2n^2 - 4n) = O(n^2).

The space complexity of your code is determined by the recursion stack. Since you have at most 2 * (n - 2) recursive calls, the maximum stack depth is proportional to n, resulting in a space complexity of O(n).