[Algotrithm] 백준 16198 에너지 모으기 python

백준 16198 문제 링크

문제 풀자마자 기쁜 마음으로 올리기 때문에 코드가 깔금하지 않습니다 ㅎㅎ

문제 설명

N개의 숫자가 주어지고 각각의 숫자는 에너지 구슬이 가지고 있는 무게를 의미한다. 하나의 에너지 구슬을 고르면 그 에너지 구슬은 삭제되고, 양 옆의 구슬의 무게를 곱해서 에너지를 얻을 수 있다. 번호는 다시 1번부터 2번 3번...n번으로 매겨야 한다.

어떻게 풀지?

보자마자 나를 포함하는 경우 / 포함하지 않는 경우 두 케이스를 생각해서 재귀로 풀어야 겠다는 생각을 했다.

선택하는 경우 -> 리스트를 copy해서 뺀 리스트를 재귀로 넘긴다.
선택하지 않는 경우 -> 인덱스만 증가 시키고 재귀로 넘긴다.

어디서 해맸지

일단, 만약 해당 원소를 삭제해서 넘긴다 쳐도 처음부터 다시 검색을 해야 하기 때문에 for문을 재귀로 돌려야 할 것 같다고 생각했다. 여기까진 좋았는데 그 다음부터 막 선택하는 경우 선택하지 않는 경우로 재귀를 두번 호출 하는데 인덱스가 잘 안맞아서 뭐 홀수 짝수 이런거 막 고민하다가.....

생각해보니까 애당초 for문을 돌면서 순서대로 해당 원소만 빠지는 경우부터 시작하기 때문에 굳이 그럴 필요가 없었다. 그냥 처음 원소부터 재귀를 잘 돌리면 되는 것이었다.

Code

import sys
from copy import deepcopy

max_val = float("-inf")

def dfs(idx,sum_val,N,w) :
    global max_val

    if  (idx-1) < 0 or (idx+1) >= len(w) or len(w) <= 2 :
    #지금 보니까 이 조건도 괜히 불필요한 부분이 있는 것 같다
        return

    for i in range(idx,len(w)-1) :    

        sum1 = sum_val+(w[i-1] * w[i+1])
        max_val = max(max_val, sum1)
        
        w_copied = deepcopy(w)
        
        del w_copied[i]

        dfs(1,sum1, N, w_copied)
        #dfs(i+1,sum_val, N, w)
        #이 친구로 뭘 해보려는 삽질을 했다.


def solve() :
    global max_val

    N = int(sys.stdin.readline())
    w = list(map(int, sys.stdin.readline().split(" ")))

    dfs(1,0,N,w)
    #0번이랑 끝번은 고르지 않기 때문에 1번부터 시작
    print(max_val)



if __name__ == "__main__" :
    solve()