알고리즘 풀이 - 백준 16198(에너지 모으기, 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

N개의 에너지 구슬이 일렬로 모였을 때, 처음과 마지막을 제외한 1개를 제외 시, 양 좌우의 곱의 에너지를 얻을 때, 이 작업을 반복하여 얻을 수 있는 최대의 에너지를 구하는 문제

 

 

2. 풀이

 

중간에 위치한 구슬을 제거하고 양 옆의 구슬의 수치를 곱하여 에너지를 획득하는 문제로, 2개만 남을 때까지 모든 경우의 수를 다 체크하여 최대가 되는 경우를 출력하는 문제이다.

재귀 방식을 사용하여 구슬을 제거하는 모든 순서를 체크하여 그 중 최대의 에너지를 얻게 되는 경우를 찾아 출력하였다. 풀이 방식은 다음과 같다.

① 각 구슬의 무게를 배열에 저장한다.
② 현재 에너지, 제거되지 않은 구슬의 수를 재귀 함수로 전달하여 수행한다.
③ Index 기준 1 ~ N-2번째 구슬을 차례대로 제거하며 에너지를 추가하고 다음 재귀 함수로 넘어간다.
④ 현재 구슬이 2개만 남을 때까지 재귀 함수를 지속하고 최대값을 갱신한다.
⑤ 갱신이 끝났으면 이전 재귀로 돌아가 이전에 제거된 구슬을 추가하고 다음 구슬을 제거하여 지속 수행한다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

import java.io.*;
import java.util.*;

public class Main{
    static int n;
    static int[] bead;
    static boolean[] used;
    static int max = 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());
        
        bead = new int[n];
        used = new boolean[n];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i < n; i++){
            bead[i] = Integer.parseInt(st.nextToken());
        }
        bruteForce(0, n);
        System.out.println(max);
        
        br.close();
    }
    
    // 에너지는 현재까지 모인 값
    // alive는 현재 제거되지 않은 구슬의 수
    private static void bruteForce(int energy, int alive){
        // 제거되지 않은 구슬이 2개라면 양 옆만 남은 것이므로 이 때 최대값을 갱신
        if(alive == 2) {
            max = Math.max(max, energy);
            // 갱신 후 반드시 이전 재귀 함수로 돌아가야 함
            return;
        }
        
        // 1~n-2번째의 구슬을 제거하는 과정을 반복문을 통해 수행
        for(int i=1; i < n-1; i++){
            // 이미 제거된 경우 넘어간다.
            if(used[i]) continue;
            
            // i번째 구슬을 제거
            used[i] = true;
            
            // 좌측 구슬 중 제거되지 않은 가장 가까운 구슬의 위치를 찾는다.
            int left_idx = i-1;
            while(used[left_idx]){
                left_idx--;
            }
            
            // 우측 구슬 중 제거되지 않은 가장 가까운 구슬의 위치를 찾는다.
            int right_idx = i+1;
            while(used[right_idx]){
                right_idx++;
            }
            
            // 양 옆의 에너지를 곱한다.
            int e = bead[left_idx] * bead[right_idx];
            
            // 현재 계산된 에너지를 재귀 함수로 전달
            bruteForce(energy + e, alive-1);
            
            // 다시 구슬을 채워넣는다.
            used[i] = false;
        }
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.