에너지 모으기

📍 문제 설명

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

16198번: 에너지 모으기

 

💡 접근

첫번째와 마지막을 제외하고 재귀를 돌면 되는 문제

현재 리스트의 인덱스를 제거하고 확인해보고 난 뒤에 해당 인덱스에 그 값을 다시 넣어줘야 한다.

 

👩‍💻 코드

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

public class Main {
    static int n, m, v, e, k, r, x, s, answer, cnt;
    static int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
    static int[] arr, dice;
    static long[] dp;
    static char[][] board;
    static boolean[][][][] visited;
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,-1,0,1};
    static ArrayList<Integer> list = new ArrayList<>();
    static StringBuilder sb;
    public static void main(String[] args) throws IOException {
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());

        arr = new int[n];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            list.add(Integer.parseInt(st.nextToken()));
        }

        T.solution(0);
        System.out.println(max);
    }

    private void solution(int sum) {
        //합칠 에너지가 없으면 그만해
        if(list.size() <= 2) {
            max = Math.max(max, sum);
        }
        else {
            for(int i = 1; i < list.size()-1; i++) {
                int temp = list.get(i);
                int mul = list.get(i-1) * list.get(i+1);
                //현재 인덱스 제거
                list.remove(i);
                solution(sum + mul);
                //그 값 해당 인덱스에 다시 넣어주기
                list.add(i, temp);
            }
        }
    }
}