[BruteForce] 백준 16198: 에너지 모으기

16198번: 에너지 모으기 (acmicpc.net)

16198번: 에너지 모으기

 

특정 에너지 구슬을 고르면, 해당 에너지 구슬 좌우 값의 곱이 에너지 총합에 추가된다.

 

한 개의 에너지 구슬을 고르면 해당 구슬은 다음 선택에서 제외된다.

 

따라서 하나의 에너지 구슬을 고를 때마다 새로 에너지 구슬 배열을 만들어서 재귀호출의 input으로 넣어 주어야 한다.

 

또한 양 끝단의 에너지 구슬은 선택될 수 없기 때문에, 탈출조건은 양 끝단 두 에너지 구슬만 남았을 때가 된다. 

 

나는 재귀함수의 parameter로 에너지 구슬 값의 배열인 energyValue, 전체 에너지 합인 energySum을 받아 다음과 같이 재귀함수를 구성하였다.

 

    static void findMaximum(int[] energyValue,int energySum){
        if(energyValue.length<=2){
            maxValue = Math.max(maxValue,energySum);
            return;
        }

        for(int i=1;i<energyValue.length-1;i++){

            energySum+=(energyValue[i-1]*energyValue[i+1]);

            //새로운 배열들 만들기
            int[] newEnergyValue = new int[energyValue.length-1];

            int tmpIdx = 0;
            for(int j=0;j<energyValue.length;j++){
                if(j!=i){
                    newEnergyValue[tmpIdx] = energyValue[j];
                    tmpIdx++;
                }
            }

            findMaximum(newEnergyValue,energySum);

            energySum-=(energyValue[i-1]*energyValue[i+1]);
        }

 

마지막 줄이 내가 이번 문제풀이를 통해 얻어간 점이다.

 

재귀호출을 일종의 트리 구조로 생각하는 법을 알게 되었다. 내가 이 문제를 틀렸던 이유 중 하나가(하나는 편한대로 억지로 쓸모없는 checked 배열을 사용하다가 삽질을 한 것) 바로 저 부분이었다.

 

재귀호출을 한 후에, 다시 energySum = 0 으로 설정하였기 때문이다. checked 배열을 사용해서 완전탐색을 할 때, 재귀호출을 불러 주고 나서 다시 checked = false로 수정해 주는 것처럼 생각했던 것 같다. 

 

실제로는 재귀호출을 한 번 진행할 때 - 그러니까 첫 번째 호출을 root로 하는 재귀호출의 tree 구조를 생각할 때 - 재귀호출을 한 번 한다는 것은 한 칸 아래로 진행한다는 것이고, 다시 호출점으로 돌아와서 다른 점에서 재귀호출을 시도하기 전에는 방금 전에 호출했던 만큼만 빼 주면 되는 것이다. 

 

내가 이전까지 다른 문제들은 어떻게 운이 좋아서 맞았던 건지도 모르겠다. 아무튼 이제는 재귀호출을 할 때, 트리구조를 그려 가면서 확실히 호출의 구조를 파악하고 작성해야겠다.

 

전체 코드 첨부하고 마친다.

import java.io.*;

public class BOJ_16198 {
    static int N;
    static int[] marbles;
    static boolean[] checked;
    static int maxValue = 0;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        marbles = new int[N];
        checked = new boolean[N];
        String[] input = br.readLine().split(" ");

        for(int i=0;i<input.length;i++){
            marbles[i] = Integer.parseInt(input[i]);
        }

        findMaximum(marbles,0);

        System.out.println(maxValue);
    }

    static void findMaximum(int[] energyValue,int energySum){
        if(energyValue.length<=2){
            maxValue = Math.max(maxValue,energySum);
            return;
        }

        for(int i=1;i<energyValue.length-1;i++){

            energySum+=(energyValue[i-1]*energyValue[i+1]);

            //새로운 배열들 만들기
            int[] newEnergyValue = new int[energyValue.length-1];

            int tmpIdx = 0;
            for(int j=0;j<energyValue.length;j++){
                if(j!=i){
                    newEnergyValue[tmpIdx] = energyValue[j];
                    tmpIdx++;
                }
            }

            findMaximum(newEnergyValue,energySum);

            energySum-=(energyValue[i-1]*energyValue[i+1]);
        }
    }

}