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

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

728x90

문제

https://www.acmicpc.net/problem/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 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 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 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 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); } } }

from http://devfunny.tistory.com/521 by ccl(A) rewrite - 2021-10-10 19:01:55