[백준 *Java] - 에너지 모으기(16198)

에너지모으기

16198번: 에너지 모으기

문제

N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다.

i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있다.

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

N과 에너지 구슬의 무게가 주어졌을 때, 모을 수 있는 에너지 양의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 에너지 구슬의 개수 N(3 ≤ N ≤ 10)이 주어진다.

둘째 줄에는 에너지 구슬의 무게 W1, W2, ..., WN을 공백으로 구분해 주어진다. (1 ≤ Wi ≤ 1,000)

출력

첫째 줄에 모을 수 있는 에너지의 최댓값을 출력한다.

---

👇 접근방식

이 문제를 읽었을 때, 조합문제이긴 한데, 어떻게 조합을 만들어서 문제를 풀 수 있을까라는 생각을 했습니다.
느낌이 dfs 백트래킹 방식으로 접근을 해야할 거 같은데? 라는 생각에서 멈추고,
테케를 가지고 어떤식으로 조합을 맞춰야하는 지 계속 적어가며 접근했습니다.

그래서 정리한 건,
문제에서 에너지 모으는 방식이라고 적어 놓은 flow를 그대로 따라가되, 
조합을 만들고 그 조합을 가지고 문제에서 언급한 로직을 직접 구현하자. 였습니다.

1. 입력받은 에너지 배열 값을 일단 배열에 저장을 해놓습니다.
2. 조합을 만드는데, 조합은 문제에서 언급한 대로, 첫 번째와 마지막을 제외한 수를 가지고 조합을 만듭니다.
3. 조합을 만드는데, 입력받은 값으로 조합을 만드는 게 아닌, 배열의 두 번째부터 마지막 수 전까지의 수를 가지고 조합을 만듭니다. ex) 1 2 3 4 5 6 7 를 에너지 구슬의 배열을 입력 받았을 시, 2~6까지 즉, 총 5개 숫자를 가지고 조합을 구성합니다.
4. 3번에서 만든 조합은 1~5를 기준으로 조합을 만들고, 만든 수를 가지고 에너지 구슬 배열의 idx로 접근을 할 생각입니다.
5. 에너지 구슬 배열에 접근할 조합을 만든 뒤, 에너지 모으기 방식 flow를 구현해서 그 쪽 로직으로 태웁니다.
6. 하나의 값이 나오면 대소 비교를 합니다.
7. 위 과정을 반복해줍니다.

여기서 중요했던 건,
입력 받은 에너지 구슬 배열의 사잇값에 접근을 하기 위한, 인덱스 배열을 하나를 만들어, 그걸 가지고 조합을 만든 뒤, 입력 받은 에너지 구슬 배열에 접근하는 것이였습니다.

 

아래의 사진은 코드를 이해하기 쉽게, 문제에서 언급한 에너지 모으기 방식을 구현한 메서드(permCalc)에서 어떤식으로 데이터가 변환되는 지의 과정을 예시를 통해 적어 놓은 것입니다.

 

아래는 성공한 코드입니다.

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

public class Boj_에너지모으기 {
    static int N;
    static ArrayList<Integer> inputData = new ArrayList<>();
    static boolean[] visited;
    static int[] idxArr;
    static int max = Integer.MIN_VALUE;


    private static void dfs(int depth, int[] perm) {
        //base case
        if (depth == N - 2) {
            permCalc(perm);
            return;
        }

        //recur
        for (int i = 0; i < N - 2; i++) {
            if (!visited[i]) {
                visited[i] = true;
                perm[depth] = idxArr[i];
                dfs( depth + 1, perm);
                visited[i] = false;
            }
        }
    }

    // 조합에 맞춰 연산 작업
    private static void permCalc(int[] perm) {
        int res = 0;
        ArrayList<Integer> copiedInputData = new ArrayList<>();
        //Collections.copy(temp, inputData); 초기화 작업 때문에 불필요한 코드라인 증가로 인해 x
        copiedInputData.addAll(inputData); // 깊은 복사
        int[] permCopy = Arrays.copyOf(perm, perm.length);

        for (int i = 0; i < permCopy.length; i++) {
            res += copiedInputData.get(permCopy[i] - 1) * copiedInputData.get(permCopy[i] + 1);
            copiedInputData.remove(permCopy[i]);
            for (int j = 0; j < permCopy.length; j++) {
                if (permCopy[i] < permCopy[j]) {
                    permCopy[j]--;
                }
            }
        }
        max = Math.max(max, res);
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        // 1. 입력 에너지 구술 배열에 저장.
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) inputData.add(Integer.parseInt(st.nextToken()));

        idxArr = new int[N-2];
        for (int i = 0; i < N-2; i++) idxArr[i] = i+1;

        visited = new boolean[N-2];
        int[] perm = new int[N-2];
        dfs(0, perm);
        System.out.println(max);
    }
}