[Baekjoon] 16198_에너지 모으기

Silver I

문제(출처: https://www.acmicpc.net/problem/16198)

---

< 에너지 모으기 >

 

문제 풀이 

 

에너지를 구할 수 있는 모든 경우를 다 구하여 에너지의 최댓값을 구한다.

 

 

 my solution (Java)

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

public class _16198_ { // 에너지 모으기
	static int arr[], result;
	static boolean visited[];

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

		int n = Integer.parseInt(bf.readLine());

		arr = new int[n];
		visited = new boolean[n];
		result = 0;

		st = new StringTokenizer(bf.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		getEnergy(0);

		System.out.println(result);
	}

	private static void getEnergy(int num) {
		int cnt = 0;
		for (int i = 1; i < arr.length - 1; i++) {
			if (!visited[i]) {
				visited[i] = true;
				int x=i, y=i;
				while(visited[x]) {
					x--;
				}
				while(visited[y]) {
					y++;
				}
				getEnergy(num + arr[x] * arr[y]);
				visited[i] = false;
			} else {
				cnt += 1;
			}
		}
		if (cnt == arr.length - 2) {
			if (result < num) {
				result = num;
			}
		}
	}
}

변수)
n : 에너지 구슬의 개수
arr : 에너지 구슬의 무게 배열
result : 에너지의 최댓값
visited : 구슬 제거 여부

 

에너지 구슬의 개수(n)와 에너지 구슬의 무게를 배열에 저장한 후 모든 경우의 수를 구하기 위해 getEnergy 함수를 호출한다.

 

첫 번째와 마지막 에너지 구슬은 고를 수 없으므로 반복문을 1부터 배열의 길이-1 전까지로 조건을 설정한다. 아직 제거되지 않은 구슬이라면 제거한다.  Wx-1, Wx+1의 구슬이 어디인지 구해서 곱을 더해주며 getEnergy 함수를 다시 호출한다. 함수 호출이 끝나면 다음 경우를 위해 구슬 제거 표시를 없앤다. 만약 모든 구슬을 제거했다면 최종 에너지 값이므로 result와 값을 비교하여 에너지의 최댓값을 구한다.  

 

최종 정답인 result를 출력한다.

---

---