[Algorithm] BaekJoon : 16198. 에너지 모으기 by Python

djagmlrhks3·2021년 2월 1일
0

Algorithm

목록 보기
86/127
post-thumbnail

[문제 바로가기] https://www.acmicpc.net/problem/16198

📌문제 설명

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

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

에너지 구슬 하나를 고른다. 고른 에너지 구슬의 번호를 x라고 한다. 단, 첫 번째와 마지막 에너지 구슬은 고를 수 없다.
x번째 에너지 구슬을 제거한다.
Wx-1 × Wx+1의 에너지를 모을 수 있다.
N을 1 감소시키고, 에너지 구슬을 1번부터 N번까지로 다시 번호를 매긴다. 번호는 첫 구슬이 1번, 다음 구슬이 2번, ... 과 같이 매겨야 한다.
N과 에너지 구슬의 무게가 주어졌을 때, 모을 수 있는 에너지 양의 최댓값을 구하는 프로그램을 작성하시오.

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

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

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


💡 문제 풀이

이 문제 역시 재귀 + DFS로 간단히 해결하였다.

에너지의 최대를 얻기위해서 그리디로 접근해보았지만 모든 경우에 대해서 탐색해야함을 느꼈다.

step 1)
변수 선언

  • numbers : 주어진 N개의 에너지 구슬의 무게를 담은 배열
  • answer : 모을 수 있는 에너지의 최대값을 담을 변수

step 2)
모을 수 있는 에너짖의 최대값을 찾기 위해 재귀함수를 만들었다(for 완전 탐색). → recursive 함수

문제 해결을 위한 진행해야하는 부분은 크게 두 가지다.

  1. 하나의 에너지 구슬을 선택하여 제거한다.
  2. 제거하려는 에너지 구슬의 왼/오른쪽에 위치한 구슬의 무게를 곱하여 에너지를 모은다.

먼저, 1번을 해결하기 위해 반복문을 이용하였다. 양 옆의 구슬의 무게를 곱하기 위해서는 인덱스의 범위는 '1 ~ 배열의길이-1'까지가 되어야 한다.
ex) [1, 2, 3, 4, 5]의 경우 제거할 수 있는 구슬은 '2', '3', '4' 3가지다.

범위에 속하는 인덱스를 대상으로 하나의 구슬을 선택하고 제거한다. 이후 양 옆에 있는 구슬의 무게를 곱하여 에너지를 모은다.

이 때, 제거한 후 배열은 '슬라이싱'을 이용해 간단하게 만들 수 있다.
ex) [1, 2, 3, 4, 5]에서 3의 무게를 가진 에너지 구슬을 제거하면 남은 구슬을 담은 배열은 [1, 2] + [4, 5]([1, 2, 4, 5]) 슬라이싱과 배열의 합으로 만들 수 있다.

step 3)
recursive 함수의 종료는 배열의 길이가 3일 때이다.

이유는 3개의 에너지 구슬이 남게되면 두 번째 에너지 구슬을 제거할 수 밖에 없고, 남은 첫 번째 구슬과 마지막 구슬을 곱하게 되면 끝이기 때문이다.
+) 에너지 구슬은 최소 3개이상이 주어진다.(N>=3)

따라서, 종료시점이 되면 마지막 연산(첫 번째 구슬 * 마지막 구슬)의 값을 누적시켜 최대값(answer)을 최신화한다.

코드는 다음과 같다.

import sys

def recursive(li, total):
    global answer
    if len(li) == 3:
        total += li[0] * li[-1]
        answer = max(answer, total)
        return

    for idx in range(1, len(li)-1):
        recursive(li[:idx] + li[idx+1:],total + li[idx-1] * li[idx+1])


N = int(input())
numbers = list(map(int, sys.stdin.readline().split()))
answer = 0

recursive(numbers[:], 0)
print(answer)

배열에서 하나(혹은 소수)의 원소를 빼는 경우 remove를 주로 이용하였었는데 파이썬의 경우 배열에서 중간에 원소가 제거되면 나머지 원소들이 빈 공간을 채우고자 이동하게 되어 시간복잡도가 증가하는 비효율이 발생한다.

따라서, 슬라이싱과 배열의 합(+)으로 진행을 하는 것이 더 효율적인 것 같다.

profile
허브

0개의 댓글