BOJ) 에너지 모으기

에너지 모으기

16198번: 에너지 모으기

풀이

 

브루트 포스 문제로 모든 경우의 수를 다 구해야 했다.

BFS와 DFS 중 DFS가 더 적절하다고 생각해서 DFS로 문제를 풀었다.

문제 조건에 따라서, 1~n-1 까지 하나의 숫자를 골라 좌 우에 있는 에너지를 곱해서 더해나갔다.

이때, 에너지를 담을 변수는 ArrayList를 선택해서 따로 index값을 복잡하게 조정하지 않게 해주었다.

왜냐하면, ArrayList에는 특정 index에 값(Element)를 넣을 수 있는 메소드가 존재하기 때문이다.

배열로 이를 구현하려면 귀찮아지니까 ArrayList를 썼다.

 

아무튼, 인덱스를 정해서 에너지를 구해서 더해준 다음 해당 인덱스를 제거하고 dfs를 돌리고, 다시 인덱스를 넣어주면서

최종적으로 2개가 남았을 때, 더한 에너지 값 중 최대값을 최신화했다.

크게 어려운 문제는 아니었다고 생각한다.

 

코드

 

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

public class GatherEnergy_16198 {
    static int answer;

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

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

        solution(n,energyList);

        br.close();
    }

    private static void solution(int n, ArrayList<Integer> energyList) {
        answer =0;
        dfs(n,energyList, 0);
        System.out.println(answer);
    }

    private static void dfs(int n, ArrayList<Integer> energyList, int sum) {
        if(n ==2) {
            answer = Math.max(answer,sum);
            return;
        }

        for(int i=1; i<energyList.size()-1; i++) {
            int mul = energyList.get(i-1)*energyList.get(i+1);
            int energy = energyList.get(i);
            energyList.remove(i);
            dfs(n-1, energyList, sum+mul);
            energyList.add(i,energy);
        }
    }
}