[JAVA]백준 16198번 에너지 모으기

📌문제 링크

---

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

📌문제 설명

---

주어진 배열에서 두 개의 가장자리를 제외한 중간 요소를 선택하여 제거하면서 최대 에너지를 모으는 문제를 해결합니다. input() 함수는 배열의 크기와 요소들을 입력받아 리스트에 저장하고, solve() 함수는 백트래킹을 시작하여 최대 에너지를 계산합니다. backTracking(int sum) 함수는 재귀적으로 호출되며, 배열의 크기가 2가 될 때까지 중간 요소를 제거하면서 에너지를 계산하고, 최댓값을 갱신합니다. 각 단계에서 현재까지의 에너지 합을 갱신하고, 제거한 요소를 복구하여 모든 가능한 경우를 탐색합니다.

📌코드

---

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

public class Main {
    // 입력을 받기 위한 BufferedReader 객체 생성
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    // 배열의 크기 (N)와 데이터를 저장할 리스트, 최대값 변수 선언
    static int N;
    static ArrayList<Integer> arr = new ArrayList<>();
    static int max = 0;

    public static void main(String[] args) throws Exception {
        input();  // 입력 데이터를 받는 메서드 호출
        solve();  // 문제 해결을 위한 백트래킹 메서드 호출
        System.out.println(max);  // 최댓값 출력
    }

    /**
     * 입력 데이터를 받아 리스트에 저장하는 메서드
     */
    public static void input() throws Exception {
        N = Integer.parseInt(br.readLine());  // 첫 번째 줄에서 N(배열 크기) 입력 받기
        StringTokenizer st = new StringTokenizer(br.readLine());  // 두 번째 줄의 숫자들을 공백 기준으로 분리

        for (int i = 0; i < N; i++) {
            arr.add(Integer.parseInt(st.nextToken()));  // 리스트에 숫자 추가
        }
        br.close();  // 입력이 끝났으므로 BufferedReader 닫기
    }

    /**
     * 백트래킹을 이용하여 최대 에너지를 구하는 메서드
     * @param sum 현재까지 계산된 에너지 합
     */
    public static void backTracking(int sum) {
        // 리스트에 남은 요소가 2개일 때 종료 (가장자리 두 개만 남았을 때)
        if (arr.size() == 2) {
            max = Math.max(max, sum);  // 최댓값 갱신
            return;
        }

        // 첫 번째와 마지막 요소를 제외한 중간 요소들을 선택하여 제거하며 탐색
        for (int i = 1; i < arr.size() - 1; i++) {
            int energy = arr.get(i - 1) * arr.get(i + 1);  // 에너지 계산 (양옆 요소의 곱)
            int temp = arr.get(i);  // 제거할 요소 저장 (백트래킹 시 복구용)

            arr.remove(i);  // i번째 요소 제거
            backTracking(sum + energy);  // 재귀 호출하여 다음 단계 탐색
            arr.add(i, temp);  // 원래 상태로 되돌림 (백트래킹)
        }
    }

    /**
     * 백트래킹 알고리즘을 실행하는 메서드
     */
    public static void solve() {
        backTracking(0);  // 초기 에너지는 0으로 시작
    }
}