[문제 바로가기] 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번을 해결하기 위해 반복문을 이용하였다. 양 옆의 구슬의 무게를 곱하기 위해서는 인덱스의 범위는 '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를 주로 이용하였었는데 파이썬의 경우 배열에서 중간에 원소가 제거되면 나머지 원소들이 빈 공간을 채우고자 이동하게 되어 시간복잡도가 증가하는 비효율이 발생한다.
따라서, 슬라이싱과 배열의 합(+)으로 진행을 하는 것이 더 효율적인 것 같다.
