[백준] 16198. 에너지 모으기 (Java)

 

문제

16198번: 에너지 모으기

 

 

알고리즘

브루트포스 알고리즘

 

 

풀이

x번째 에너지 구슬을 제외하는데 첫 번째와 마지막 에너지 구슬은 고를 수 없으므로 총 N-2 개의 구슬을 제거해야한다.

N이 최대 10이므로 N-2 는 최대 8이고, 즉 최대 8개의 구슬 중 제거할 구슬의 순서를 정하는 일이므로 경우의 수는 8! = 약 40,000 개이다.

따라서 전체 경우의 수를 탐색해 에너지 양의 최댓값을 구한다.

 

에너지 구슬을 고르면 그 구슬은 제거되므로 이미 제거된 구슬인지 확인하기 위한 boolean형 변수 visited를 만든다.

 

2번째 구슬부터 N-1 번째 구슬까지 다음 과정을 반복한다.

1. i번째 구슬이 이미 선택(제거)되었다면 continue

2. 선택된 적이 없다면 해당 구슬의 왼쪽, 오른쪽의 제거되지 않은 가장 가까운 구슬 탐색(Wx-1, Wx+1)

3. Wx-1 * Wx+1 을 sum에 합산

4. 해당 구슬 제거 (visited[i] = true)

5. 다음 구슬 선택 진행

 

위 과정을 N-2번 완료하면 모든 구슬을 고른 것이므로 그때의 sum 값을 최댓값과 비교하여 갱신한다.

 

for (int i = 1; i < N - 1; i++) {
	if (visited[i]) continue;

	visited[i] = true;
	int left = i - 1;
	int right = i + 1;

	while (visited[left]) left--;
	while (visited[right]) right++;

	dfs(count + 1, sum + W[left] * W[right]);
	visited[i] = false;
}

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int N, W[], max;
	static boolean visited[];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		W = new int[N];
		visited = new boolean[N];
		max = 0;

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++)
			W[i] = Integer.parseInt(st.nextToken());

		dfs(0, 0);

		System.out.println(max);
	}

	private static void dfs(int count, int sum) {

		if (count == N - 2) {
			max = Math.max(max, sum);
			return;
		}

		for (int i = 1; i < N - 1; i++) {
			if (visited[i]) continue;

			visited[i] = true;
			int left = i - 1;
			int right = i + 1;

			while (visited[left]) left--;
			while (visited[right]) right++;

			dfs(count + 1, sum + W[left] * W[right]);
			visited[i] = false;
		}
	}
}