[코테] 백준 재귀 16198번 문제

16198번 : 에너지 모으기

문제 링크

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

문제 설명

N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다.

i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있다.

1. 에너지 구슬 하나를 고른다. 고른 에너지 구슬의 번호를 x라고 한다. 단, 첫 번째와 마지막 에너지 구슬은 고를 수 없다.
2. x번째 에너지 구슬을 제거한다.
3. Wx-1 × Wx+1의 에너지를 모을 수 있다.
4. N을 1 감소시키고, 에너지 구슬을 1번부터 N번까지로 다시 번호를 매긴다. 번호는 첫 구슬이 1번, 다음 구슬이 2번, … 과 같이 매겨야 한다.

N과 에너지 구슬의 무게가 주어졌을 때, 모을 수 있는 에너지 양의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 에너지 구슬의 개수 N(3 ≤ N ≤ 10)이 주어진다.

둘째 줄에는 에너지 구슬의 무게 W1, W2, …, WN을 공백으로 구분해 주어진다. (1 ≤ Wi ≤ 1,000)

출력

첫째 줄에 모을 수 있는 에너지의 최댓값을 출력한다.

문제풀이

고른 구슬 이전/이후 구슬을 선택할 때 이미 제거된 구슬을 건너뛰어야 하는것을 유의하며 풀이한다.

maxValue = 0
def max_energy(temp, result) :
    global maxValue

    # 남은 에너지 구슬이 2개이면 최대값 갱신
    if len(temp) == N-2 :
        maxValue = max(maxValue, result) 
        return

    # 2번부터 N-1까지 구슬을 순회하며 재귀 진행 (맨처음, 맨마지막 구슬은 고를수 없음)
    for i in range(1, N-1) :

        # 이전에 넣은 구슬이 아닐 경우 아래 조건 실행
        if i not in temp : 

            # 이전 구슬, 이후 구슬은 이미 제거된 구슬을 건너뛰어야함
            prev, next = i-1, i+1
            while prev in temp :
                prev -= 1
            while next in temp : 
                next += 1

            # 이전 구슬 x 이후 구슬을 진행 및 재귀 진행
            temp.append(i)
            result += beads[prev] * beads[next]

            max_energy(temp, result)
            
            temp.pop()
            result -= beads[prev] * beads[next]
    
    return maxValue

N = int(input())
beads = list(map(int, input().split()))
print(max_energy([], 0))