[Baekjoon 16198번] 에너지 모으기 문제 (with 자바)

문제

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

16198번: 에너지 모으기

 

 

 

풀이코드(실패)

package seohae.algorithm.level2;

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * https://www.acmicpc.net/problem/15658
 */
public class Problem_019_16198 {
    public static List<Integer> list;
    static int N; /* 열 개수 */
    static boolean[] visited; //스킵 판별
    static int resultSum = 0;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 열 개수
        list = new ArrayList<>();
        visited = new boolean[N];

        for(int i = 0; i < N; i++) {
            list.add(sc.nextInt());
        }

        dfs(1); /* 맨 첫번째 요소 제외 */

        System.out.println(resultSum);
    }

    static void dfs(int value) {

        /* 종료 */
        if (list.size() == 2) {
            return;
        }

        int sum = 0;
        int sumIdx = 0;

        for (int i = value; i < list.size() - 1; i++) {
            int targetSum = list.get(i - 1) * list.get(i + 1);

            if (sum < targetSum) {
                sum = targetSum;
                sumIdx = i;
            } else if (sum == targetSum) {
                if (sumIdx > i) {
                    sumIdx = i;
                }
            }
        }

        /* 제거 */
        resultSum += sum;
        list.remove(sumIdx);

        dfs(1);

    }
}

 

백준 문제에 제공되는 테스트는 모두 통과한다. 하지만 제출시, 실패하는 코드다. 반례로, 아래의 경우에는 정답이 아니다.

 

반례

5
3 1 2 4 5

 

이때 위 코드대로 실행된다면, 4 -> 1 -> 2 순으로 뽑게되어 10 + 6 + 15 = 31 이 나오게되는데, 정답은 1 -> 2 -> 4 순으로 뽑게되어 6 + 12 + 15 = 33 이 나와야한다. 무조건적으로 양 옆의 곱의 결과가 크다고 먼저 뽑은 결과는 문제에서 원하는 결과가 아니다.

 

아래 정답코드를 보면 결국 모든 경우의수를 재귀함수를 통해 구하여 List 에 담고 마지막으로 max 값을 꺼내 출력하게된다.

 

 

 

풀이코드(정답)

package seohae.algorithm.level2;

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * https://www.acmicpc.net/problem/15658
 */
public class Problem_019_16198_정답 {
    public static List<Integer> resultList = new ArrayList<>();
    static int N; /* 열 개수 */
    static boolean[] visited; //스킵 판별
    static int resultSum = 0;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 열 개수
        visited = new boolean[N];

        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < N; i++) {
            list.add(sc.nextInt());
        }

        dfs(list, 0); /* 맨 첫번째 요소 제외 */

        System.out.println(resultList.stream()
                .mapToInt(x -> x)
                .max().getAsInt());
    }

    static void dfs(List<Integer> list, int sum) {

        /* 종료 */
        if (list.size() == 2) {
            if (resultSum < sum) {
                resultSum = sum;
            }

            resultList.add(resultSum);
            resultSum = 0;

            return;
        }

        for (int i = 1; i < list.size() - 1; i++) {
            int temp = list.get(i);
            int targetSum = list.get(i - 1) * list.get(i + 1);

            /* 제거 */
            list.remove(i);

            dfs(list, targetSum + sum);

            list.add(i, temp);
        }

    }
}

 

list 를 파라미터로 함께 호출해야하는건 필수다. target (i) 가 remove 된 리스트로 재귀호출이 되어야하고, 끝났을 경우 다시 해당 값을 add 한 리스트로 호출되야하기 때문이다.