[실버 1] 백준 16198 - 에너지 모으기 (파이썬)

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

풀이

• 구슬이 일렬로 놓여 있고, 양끝 구슬을 제외하고 하나를 고를 수 있다.
• 고른 구슬을 제거하면서 얻는 에너지는 (왼쪽 구슬 번호) * (오른쪽 구슬 번호)
• 구슬이 2개 남을때까지 반복
• 얻을 수 있는 에너지의 최대값을 구하라

if len(a) == 2:
    return w

구슬이 2개만 남으면 더이상 고를 수 없으니, 지금까지 모은 에너지를 반환한다.

재귀 호출은 다음과 같이 진행한다.

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

맨 앞과 맨 뒤 구슬을 제외한 가운데 구슬만 고를 수 있다.

na = a[:i] + a[i+1:]

i번째 구슬을 제거해서 새로운 리스트를 만든다.

tmp = dfs(na, w + a[i-1] * a[i+1])

i번째 구슬을 제거했을 때 생기는 에너지를 추가한 다음, 나머지 구슬로 다시 dfs를 호출한다.

if ret < tmp:
    ret = tmp

모든 경우를 다 탐색해서 최대 에너지 값을 고른다.

코드

# 백준 16198 - 에너지 모으기
# 분류 : 브루트포스, 재귀
 
N = int(input())
A = list(map(int, input().split()))
 
def dfs(a, w) :
    if len(a) == 2 :
        return w
    
    ret = 0
    for i in range(1, len(a) - 1) :
        na = a[ : i] + a[i + 1 :]
        tmp = dfs(na, w + a[i - 1] * a[i + 1])
        if ret < tmp :
            ret = tmp
    
    return ret
 
print(dfs(A, 0))