백준 16198 : 에너지 모으기 (Python)

본문 링크

def BackTracking(total , L ):
    global Answer

    Answer=max(Answer,total)

    if len(L)>=3:
        for i in range(1,len(L)-1):
            count=L[i-1]*L[i+1]
            check=(i,L[i])
            del L[i]
            BackTracking(total+count , L )
            L.insert(check[0] , check[1] )


N=int(input())

L=list(map(int,input().split()))
Answer=0
BackTracking( 0 , L )

print(Answer)

📌 어떻게 접근할 것인가?

모든 경우의 수를 탐색할 수 있는 백트래킹을 사용해 풀었습니다.

if len(L)>=3:
	for i in range(1,len(L)-1):
		count=L[i-1]*L[i+1]
		check=(i,L[i])
		del L[i]
		BackTracking(total+count , L )
		L.insert(check[0] , check[1] )

리스트의 길이가 $3$ 이상일때 , 시작과 끝을 제외한 나머지 원소들에 대해 반복문으로 탐색을 시작합니다.

왼쪽원소와 오른쪽원소의 곱을 저장하고 , check 변수에 원소를 지울려는 인덱스와 , 그때의 값을 저장합니다.

이후 del L[i] 를 통해 원소를 삭제하는데

이때 remove 를 사용해서는 안됩니다.

L.remove(L[i]) 를 해버리면 리스트에 중복된 값들이 여러개있을때 , 가장 왼쪽에있는 원소를 지우게 됩니다. 따라서 del 을 사용했습니다.

이후 재귀가 끝나면 다시 원소를 insert 를 통해 넣어주었습니다.

Answer=max(Answer,total)

$Answer$ 변수를 통해 매번 최대값을 갱신해주고 재귀가 끝나면 $Answer$ 를 출력해줍니다.