백준-16198번/에너지 모으기(java)

 

 

문제 이해

1. 에너지 구슬 하나를 고른다. 고른 에너지 구슬의 번호를 x라고 한다. 단, 첫 번째와 마지막 에너지 구슬은 고를 수 없다.
2. x번째 에너지 구슬을 제거한다.
3. Wx-1 × Wx+1의 에너지를 모을 수 있다.
4. N을 1 감소시키고, 에너지 구슬을 1번부터 N번까지로 다시 번호를 매긴다. 번호는 첫 구슬이 1번, 다음 구슬이 2번, ... 과 같이 매겨야 한다.

ex)

5
100 2 1 3 100

 

2제거 ==> 에너지 : 100*1=100

1제거 ==> 에너지 : 100 + (100*3) = 400

3제거 ==> 에너지 : 400+(100*100) =10400

 

에너지 구슬이 2개가 남으면 아무 구슬도 선택할 수 없으므로 종료

 

이 문제는 모든 경우의 에너지를 구해야 하는 문제이므로 백트래킹을 구현하여 모든 경우의 수에서 나올 수 있는 에너지 값중 최대값을 구할 수 있다.

 

문제 해결

 

static ArrayList<Integer> list=new ArrayList<>();
static int N;
static int Max=Integer.MIN_VALUE;

에너지 구슬들을 저장할 수 있도록 ArrayList를 사용했다.

 

static void dfs(int value){
    if(list.size()==2){
        if(value>Max){
            Max=value;
        }
        return;
    }
   for(int i=1; i<list.size()-1; i++){
       int energy=(list.get(i-1)*list.get(i+1));
       int n=list.remove(i);
       dfs(value+energy);
       list.add(i,n);
   }
}

구슬의 갯수가 2개 남으면 재귀를 종료하고 그때의 value값이 최대값이면 최대값을 갱신해준다.

 

주의할 점: 구슬을 삭제하고 재귀호출을 하면 그 구슬말고 다른 구슬을 먼저 삭제했을때의 경우도 구해줘야 하므로 list에 삭제했던 구슬을 다시 추가해줘야 한다.