[백준_16198번] 에너지 모으기

https://www.acmicpc.net/problem/16198

16198번: 에너지 모으기

[문제]

 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있다.

 

1. 에너지 구슬 하나를 고른다. 고른 에너지 구슬의 번호를 x라고 한다. 단, 첫 번째와 마지막 에너지 구슬은 고를 수 없다.
2. x번째 에너지 구슬을 제거한다.
3. Wx-1 × Wx+1의 에너지를 모을 수 있다.
4. N을 1 감소시키고, 에너지 구슬을 1번부터 N번까지로 다시 번호를 매긴다. 번호는 첫 구슬이 1번, 다음 구슬이 2번, ... 과 같이 매겨야 한다.

 N과 에너지 구슬의 무게가 주어졌을 때, 모을 수 있는 에너지 양의 최댓값을 구하는 프로그램을 작성하시오.

 

[입력 조건]

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

 

[코드]

import java.util.*;

public class BaekJoon_16198 {
	static ArrayList<Integer> energy=new ArrayList<>();
	static int n,max=0;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		
		for(int i=0;i<n;i++)
			energy.add(sc.nextInt());
		
		dfs(0);
		System.out.println(max);
		
	}
	static void dfs(int sum) {
		// 첫 번째와 마지막 에너지 구슬만 남게 된다면 최댓값 갱신
		if(energy.size()==2) {
			max=Math.max(max, sum);
			return;
		}
		
		// 첫 번째와 마지막 에너지 구슬은 선택할 수 없기 때문에 그 사이의 인덱스만 선택
		for(int i=1;i<energy.size()-1;i++) {
			int temp=energy.get(i); 
			int cal=energy.get(i-1)*energy.get(i+1); // 모인 에너지 계산
			energy.remove(i); // i번째 에너지 구슬 제거
			dfs(sum+cal); // 모인 에너지만큼 누적한 뒤 재귀호출
			energy.add(i, temp); // 다음 경우의 수를 위해 제거한 위치에 다시 삽입
		}
	}
}

 

[고찰]

 이번 문제는 백트래킹을 사용하여 모든 경우의 수를 확인하는 문제이다. 이때 에너지 구슬의 위치를 변경해야 하는 과정이 있기 때문에 배열보다는 연결리스트를 사용하는 것이 더 효율적이라고 생각했다. 따라서 i번째 에너지 구슬을 선택해서 제거했다면 재귀호출 뒤에 다시 i번째 인덱스에 삭제했던 에너지 구슬을 삽입해야 한다. 자바 라이브러리에는 이와 같은 기능을 하는 함수를 제공하기 때문에 쉽게 해결할 수 있었다.