알고리즘 문제 해결 전략 - 동적 계획법
https://algospot.com/judge/problem/read/NUMBERGAME
cache[left][right]
: 전체 보드(배열)을 기준으로 [left, right] 범위 부분 배열 상태
maxDiff(left, right)
: [Left, right] 부분 배열에서 진행될 때
(현재 플레이어 점수 - 상대 플레이어 점수)의 최대값
maxDiff(left, right) =
MAX (
arr[left] - maxDiff(left+1, right), //왼쪽 점수 가져가기
arr[right] - maxDiff(left, right-1), //오른쪽 점수 가져가기
-maxDiff(left+2, right), //왼쪽 2개 제거
-maxDiff(left, right-2) //오른쪽 2개 제거
)
왼쪽 점수 가져가기
를 통해 예로 들면 아래와 같은 식이 성립하기 때문이다.현재 플레이어를 A, 다음 플레이어를 B라고 할때
maxDiff(left, right)상태에서
arr[left] - maxDiff(left+1, right)
= 가장 왼쪽 점수 - (B점수 - A점수의 최대값)
= 가장 왼쪽 점수 + A점수 - B점수
import java.util.Scanner;
public class Main {
public static int C, N;
public static int [] arr = new int[51];
public static int[][] cache = new int[51][51];
public static int INF = 987654321;
public static int maxDiff(int left, int right) {
//기저 사례 : 수가 하나도 남지 않았을 때
if (left > right) return 0;
//다이나믹 프로그래밍
if (cache[left][right] != -INF) return cache[left][right];
int maxValue = -INF;
//4가지 상황 고려
//1. 왼쪽 수 하나 가져가기
maxValue = Math.max(maxValue, arr[left] - maxDiff(left + 1, right));
//2. 오른쪽 수 하나 가져가기
maxValue = Math.max(maxValue, arr[right] - maxDiff(left, right - 1));
if (right - left + 1 >= 2) {
//3. 왼쪽 수 두개 제거
maxValue = Math.max(maxValue, -maxDiff(left+2, right));
//4. 오른쪽 수 두개 제거
maxValue = Math.max(maxValue, -maxDiff(left, right-2));
}
cache[left][right] = maxValue;
return cache[left][right];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
C = sc.nextInt();
for (int c = 0; c < C; c++) {
N = sc.nextInt();
//초기화
for (int i = 0; i < N; i++) {
arr[i] = sc.nextInt();
for (int j = 0; j < N; j++)
cache[i][j] = -INF;
}
//메인 함수 실행
System.out.println(maxDiff(0, N-1));
}
}
}