https://www.acmicpc.net/problem/11062
11062번: 카드 게임
근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는
www.acmicpc.net
N이 1000이기 때문에 브루트포스를 수행하면 2^500으로 시간초과가 난다. 어떻게 연산을 줄일 수 있을까 고민하다 다이나믹 프로그래밍까지 떠올리긴 했지만 점화식을 세우기 어려웠다.
우선 이 문제는 모든 경우의 수를 탐색해야 한다. 왼쪽과 오른쪽을 고른 경우가 각각 최대 점수를 얻는게 달라지기 때문이다. 즉, 근우의 차례엔 근우의 점수가 최대가 되게 하고, 명우의 차례엔 근우의 점수가 최소가 되도록 해야 한다.
문제의 조건을 유심히 보면 부분 문제가 있는걸 알 수 있는데, dp[l][r] = l~r번째 카드 중에서 근우가 얻을 수 있는 최대 점수로 테이블을 구성하여 이미 구한 값을 재사용하도록 했다.
import java.io.*;
import java.util.*;
public class Main {
public static int T, N;
public static int[] card;
public static int[][] dp;
public static int Game(int l, int r, int t){
if(l > r) return 0;
if(dp[l][r] != 0) return dp[l][r];
if(t % 2 != 0)
return dp[l][r] = Math.max(card[l] + Game(l + 1, r, t + 1), card[r] + Game(l, r - 1, t + 1));
else
return dp[l][r] = Math.min(Game(l + 1, r, t + 1), Game(l, r - 1, t + 1));
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
T = Integer.parseInt(st.nextToken());
while(T-- != 0){
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
card = new int[N]; dp = new int[N][N];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++)
card[i] = Integer.parseInt(st.nextToken());
System.out.println(Game(0, N - 1, 1));
}
}
}
'알고리즘 관련 > BOJ' 카테고리의 다른 글
1967 트리의 지름 구하기 (0) | 2022.02.03 |
---|---|
1916 최소비용 구하기 (0) | 2022.02.03 |
22254 공정 컨설턴트 호석 (0) | 2022.01.06 |
1938 통나무 옮기기 (0) | 2021.12.27 |
9205 맥주 마시면서 걸어가기 (0) | 2021.12.27 |