[baekjoon] 백준 16198번(파이썬): 에너지 모으기

문제

16198번: 에너지 모으기

알고리즘

- 백트래킹을 통해 문제를 수행한다.

- 에너지 구슬이 2개일 때까지 재귀적으로 탐색을 한다.

- 에너지 구슬이 2개가 되면 그때의 최대 에너지 값으로 초기화한다.

- 에너지 구슬이 2개가 아니라면 반복문을 통해 에너지 구슬을 확인한다.

여기서부터 백트래킹 부분

- i번째 구슬을 제거했을 때 나오는 에너지를 가지고 재귀적으로 탐색

- 재귀적인 탐색이 끝났다면 제거한 에너지 구슬을 추가하고 다시 반복한다.

- 재귀적으로 탐색하는 과정에서 에너지를 모을 수 있는 모든 경우를 탐색한다.

- 최대 에너지 값을 출력한다.

코드

import sys


def back_tacking(x):
    global answer

    # 에너지를 모았다면 answer와 비교하여 초기화
    if len(w) == 2:
        answer = max(answer, x)
        return

    # 반복문을 통해 에너지 구슬을 확인
    for i in range(1, len(w) - 1):
        target = w[i - 1] * w[i + 1] # i번째 구슬을 제거했을 때 나오는 에너지

        # 백트래킹
        v = w.pop(i) # 에너지 구슬 제거
        back_tacking(x + target) # 제거된 구슬로 에너지를 재귀적으로 탐색
        w.insert(i, v) # 제거한 에너지 구슬 추가


n = int(sys.stdin.readline())
w = list(map(int, sys.stdin.readline().split()))
answer = 0
back_tacking(0)
print(answer)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법