[백준] 16198 에너지 모으기 - 백트래킹 JAVA

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

16198번: 에너지 모으기

코드설명

백트래킹 문제입니다.

 

ArrayList를 활용하여 에너지 구슬의 arr을 remove하고 원상복구(add) 해주는 과정을 통해서 모든 경우의수를 다 구해주었습니다.

저 같은경우 startIdx, 아래와 같이 삭제하려는 에너지 구슬의 위치를 가지고 다니면서 진행했습니다.

for(int i=1;i<N-1;i++) {
    simulate(0, i, 0);	
}

 

다른 분들의 코드도 함께 확인해보니 아예 DFS에서 for문으로 한번에 처리한 코드들이 있습니다.

해당 코드도 한번 최적화하여 수정해보았습니다.

코드

최적화코드, for문의 i로 모두 처리합니다.

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

public class Main {
	
	public static int N, M;
	
	public static ArrayList<Integer> arr = new ArrayList<Integer>();
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr.add(Integer.parseInt(st.nextToken()));
    	}
    	
    	simulate(0, 0);	
		
    	System.out.println(answer);
    }
    
    public static void simulate(int level, int sum) {
    	if(level == N-2) {
    		answer = Math.max(answer, sum);
    		return ;
    	}
    	
    	for(int i=1; i<arr.size()-1;i++) {
    		int result = arr.get(i - 1) * arr.get(i + 1);
    		int storeValue = arr.get(i);
        	arr.remove(i);
    		simulate(level+1, sum + result);
    		arr.add(i, storeValue);
    	}
    	
    }
    
    
}

처음에 푼 최적화하지 않은 코드, startIdx를 가지고다니면서 범위체크도 진행합니다.

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

public class Main {
	
	public static int N, M;
	
	public static ArrayList<Integer> arr = new ArrayList<Integer>();
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr.add(Integer.parseInt(st.nextToken()));
    	}
    	
    	for(int i=1;i<N-1;i++) {
    		simulate(0, i, 0);	
    	}
		
    	System.out.println(answer);
    }
    
    public static void simulate(int level, int startIdx, int sum) {
    	if(level == N-2) {
    		answer = Math.max(answer, sum);
    		return ;
    	}
    	if(startIdx == 0 || startIdx >= arr.size() - 1) return ;
    	
    	for(int i=1; i<arr.size()-1;i++) {
    		int result = arr.get(startIdx - 1) * arr.get(startIdx + 1);
    		int storeValue = arr.get(startIdx);
        	arr.remove(startIdx);
    		simulate(level+1, i, sum + result);
    		arr.add(startIdx, storeValue);
    	}
    	
    }
    
}