티스토리 뷰

[BOJ 11062] 카드 게임


이 문제를 풀면서 재귀함수를 이용한 탑다운 dp가 훨씬 편리하다는 것을 뼈저리게 느꼈다. 예전부터는 dp문제를 모두 for문으로 짜려고 고집했는데 이제부터는 재귀함수를 자주 활용해야겠다. 선택의 여지에 따라서 앞으로의 결과가 달라지는 유형의 문제를 이 방식으로 풀면 편하다. 이 문제의 경우, 왼쪽의 카드를 뽑을 것이냐 오른쪽의 카드를 뽑을 것이냐 이렇게 두 가지의 선택지가 있는 것처럼 말이다. 

이 문제에서 한가지 막혔던 부분은 나의 최적의 경우와, 상대의 최적의 경우를 어떻게 동시에 고려하느냐였는데 나의 최적일 때는 max를 취하고, 상대의 최적일 때는 min을 취하면 된다. 나의 min의 경우와 상대의 max의 경우가 곧 동치이기 때문이다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<stdio.h>
#include<algorithm>
using namespace std;
#define SIZE 1009
 
int arr[SIZE],dp[SIZE][SIZE];
 
int rec(int turn,int l,int r){
    if(dp[l][r]!=-1return dp[l][r];
    if(l>r) return 0;
 
    int &ret=dp[l][r];
    if(turn%2){
        ret=max(rec(turn+1,l+1,r)+arr[l],rec(turn+1,l,r-1)+arr[r]);
    }
    else{
        ret=min(rec(turn+1,l+1,r),rec(turn+1,l,r-1));
    }
    
    return ret;
}
int main(){
    int t;  scanf("%d",&t);
 
    while(t--){
        int n;  scanf("%d",&n);
 
        for(int i=1 ; i<=n ; i++)
            for(int j=1 ; j<=n ; j++)
                dp[i][j]=-1;
 
        for(int i=1 ; i<=n ; i++)
            scanf("%d",&arr[i]);
 
        int ans=rec(1,1,n);
        printf("%d\n",ans);
    }
    return 0;
}
cs


'Problem Solving > Dynamic Programming' 카테고리의 다른 글

[Codeforces 1084C] The Fair Nut and String  (0) 2019.02.02
[BOJ 2618] 경찰차  (0) 2019.01.29
[BOJ 1695] 팰린드롬 만들기  (0) 2019.01.23
[BOJ 1328] 고층 빌딩  (0) 2019.01.22
[BOJ 2281]데스노트  (0) 2019.01.18
댓글