16198번 - 에너지 모으기

문제요약

1. 주어진 구슬중 1개를 선택하면 좌, 우 구슬의 무게의 곱만큼 에너지를 얻는다. (단 양쪽 끝의 구슬은 선택할 수 없다.)
2. 선택한 구슬을 전체 구슬에서 빼낸다.
3. 전체 구슬의 개수가 2개 이하가 될 때까지 반복한다.

원본 문제 보러가기

접근법

만약 [3, 5, 2, 1, 7] 이라는 구슬들이 있다고 했을 때 1번 구슬을 빼면 [3, 5, 2, 7] 이 되고 얻어진 에너지는 2 * 7인 14가 된다. 아직 구슬의 개수가 2개 이상이기 때문에 다음 구슬을 뺄 수 있다. 5번 구슬을 빼면 [3, 2, 7] 이 되고 얻어진 에너지는 2 * 3인 6이 된다. 전에 14라는 에너지를 얻었고 이번에 6이라는 에너지를 얻었기 때문에 총 20이라는 에너지를 얻었다. 마지막으로 2라는 구슬을 빼면 3 * 7인 21만큼 에너지를 얻어 총 41에너지를 획득한다.

이런 과정을 반복할 때 얻을 수 있는 총 에너지의 값을 계산하는 문제로 이 문제를 풀기 위해 완전 탐색을 사용했다. 재귀함수를 이용하여 각각의 구슬을 1개씩 빼본다. 1개를 뺀 상태에서 다시 재귀함수를 이용하여 구슬을 빼본다. 이 과정을 전체 구슬의 개수가 2개 이하가 될 때까지 반복한다. 이렇게 해서 얻을 수 있는 총 에너지를 모두 계산한다. 이렇게 계산된 총 에너지중 가장 큰값을 가진 총 에너지를 선택하여 출력하면 문제를 풀 수 있다.

[3, 5, 2, 1, 7] 이라는 구슬들을 가지고 있을 때 얻을 수 있는 총 에너지의 집합은 [41, 61, 70]이 된다. 얻을 수 있는 총 에너지에 차이가 나는 이유는 구슬을 뽑는 순서가 결과에 영향을 주기 때문이다. 70을 출력하면 답을 얻을 수 있다.

pseudocode

  def energy(beads):
    if number of beads is less than 2 or equal with 2:
      return 0

    for idx from second to last - 1:
      energy = max(energy, energy(beads.pop(idx)) + bead[idx - 1] * bead[idx + 1])

    return energy