백준 16198번: 에너지 모으기

문제 설명

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

접근법

• N이 10으로 작기 때문에 모든 경우의 수를 구해도 10!(3_628_800)으로 제한시간 내에 해결 가능합니다.
  실제로는 N이 10일 때 8개의 값을 빼기 때문에 8!으로 더 낮은 시간 복잡도로 문제를 해결할 수 있습니다.
• 모든 경우의 수를 계싼하여 정답을 구합니다.

정답

import java.util.*;

public class Main {
	static int maxVal = -1;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		List<Integer> lst = new ArrayList<Integer>();

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

		recursion(0, N, 0, lst);
		System.out.println(maxVal);
	}

	public static void recursion(int depth, int N, int answer, List<Integer> lst) {
		if (depth == N - 2) {
			maxVal = Math.max(answer, maxVal);
			return;
		}
		for (int i = 1; i < lst.size() - 1; i++) {
			int leftNum = lst.get(i - 1);
			int rightNum = lst.get(i + 1);
			int num = lst.remove(i);
			recursion(depth + 1, N, answer + leftNum * rightNum, lst);
			lst.add(i, num);
		}
	}

}

기타

• 현재 list에서 가장 큰 값을 구하도록 계산하면 틀리는 이유
  • 반례: https://www.acmicpc.net/board/view/78157
    [10 7 8 9 10 2 4 13]숫자에서 [2, 4, 10, 9, 8, 7] 순서로 값을 제외했을 때 570이 아닌 612가 나옴