백준: 16198 에너지 모으기

문제

16198번: 에너지 모으기

 

문제 풀이

 문제는 구슬들 중에 특정 구슬을 제거하고, 제거한 구슬 주위의 값들을 곱하는 방식을 통해 구슬이 2개가 될 때까지 계속해서 진행하여 제거하는 경우에 따라 가장 큰 값을 가지는 경우를 반환하는 문제이다. 문제에서 발생할 수 있는 경우의 수는 위의 그림과 같이 생각할 수 있다.

 

 그림은 예제 입력 1에서 발생할 수 있는 경우의 수를 나타낸 경우이다. 구슬이 4개 이므로 발생할 수 있는 경우의 수는 2가지가 된다. 그림에서 알 수 있듯이 어떤 구슬을 먼저 제거하느냐에 따라 경우의 수가 달라진다는 것을 알 수 있다. 따라서 백트랙킹을 통해 각 경우의 수를 찾으면 된다.

 

코드

from sys import stdin


def dfs(sum_bead):
    global answer

    if len(beads) == 2:
        answer = max(answer, sum_bead)
        return

    for i in range(1, len(beads) - 1):
        value = beads[i - 1] * beads[i + 1]
        origin = beads[i]
        del beads[i]
        dfs(sum_bead + value)
        beads.insert(i, origin)


if __name__ == '__main__':
    answer = 0
    n = int(stdin.readline())
    beads = list(map(int, stdin.readline().split()))
    dfs(0)
    print(answer)

 `visited` 배열을 통해 각 인덱스의 방문 여부를 체크하고, i 값을 계산하여도 되지만 n이 최대 10이므로 `insert`, `del`에 대한 오버헤드가 크지 않으므로 이해하기 쉽고 간편한 방식을 사용하였다.