티스토리 뷰
이 문제를 풀면서 재귀함수를 이용한 탑다운 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]!=-1) return 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 |