P.16198 에너지 모으기

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;

public class P_16198 {

    static int max = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        ArrayList<Integer> energy = new ArrayList<>();
        for (int i : arr) {
            energy.add(i);
        }

        energy_supply(energy, n,1, 0);

        bw.write(Integer.toString(max));
        bw.flush();
    }

    public static void energy_supply(ArrayList<Integer> energy, int total, int idx, int sum) {
        if (idx == total - 1) {
            if (max < sum) max = sum;
            return ;
        }

        int supply = energy.get(idx - 1) * energy.get(idx + 1);
        ArrayList<Integer> n_energy = new ArrayList<>();
        for (Integer integer : energy) {
            n_energy.add(integer);
        }
        n_energy.remove(idx);
        energy_supply(n_energy, total - 1, 1, sum + supply);

        energy_supply(energy, total, idx + 1, sum);
    }
}

코드 설명

재귀를 이용해서 풀었다.

 

일렬로 있는 에너지는 선택되거나, 선택되지 않거나 둘 중 한가지를 택해야 한다.

만약, 선택된다면 해당 에너지는 그 열에서 지워지게 되고 양쪽에 있는 에너지를 곱한 만큼 에너지를 수급하게 된다.

삭제를 용이하게 하기 위해 배열이 아닌 arraylist를 사용했다.

배열을 이용할 경우 삭제를 할 시 모든 인덱스를 수동으로 당겨와야 하기 때문에 비효율적이다.

그리고, 선택이 될 경우 해당 에너지가 삭제된 arraylist를 넘겨줘야하는데 얕은 복사일 경우 원본 arraylist도 손상되기 때문에 깊은 복사를 해서 넘겨주었다.

삭제를 할 경우, 다시 인덱스가 1인 에너지부터 검사를 할 수 있도록 했다.

 

선택을 하지 않았을 경우 아무 변화 없고, idx + 1만해서 다음 에너지를 검사할 수 있도록 재귀함수를 호출한다.