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

📌 문제

알고리즘 분류 : 백트레킹
난이도 : 실버1
출처 : 백준 - 에너지 모으기

🦧 문제 풀이 접근

linkedlist에 구슬 데이터를 넣고 재귀함수를 통해 한개씩 제거, 추가 하면서 모든 가능한 경우에 점수를 계산했다.

💻 code

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

public class Main {
    static int maxSum = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        LinkedList<Integer> linkedList = new LinkedList<>();
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<N;i++) {
            linkedList.add(Integer.parseInt(st.nextToken()));
        }
        req(0,linkedList);
        System.out.println(maxSum);
    }
    private static void req(int tempSum, LinkedList<Integer> linkedList) {
        if(linkedList.size()==2) {
            maxSum = Math.max(maxSum,tempSum);
            return;
        }
        for(int i=1;i<linkedList.size()-1;i++) {
            int exceptNum = linkedList.get(i);
            linkedList.remove(i);
            req(linkedList.get(i-1) * linkedList.get(i) + tempSum,linkedList);
            linkedList.add(i,exceptNum);
        }
    }
}

🥇 결과

🎓 느낀점

linkedlist에 구슬을 넣고 백트레킹을 해서 추가, 삭제를 빠르게 할 수 있었다.