[BAE/<JOON> 문제풀이] 10835. 카드게임

https://www.acmicpc.net/problem/10835

10835번: 카드게임

처음에 일반적인 n*n 포문으로 점화식 짜서 풀었다.

 

근데 자꾸 틀려서 코너케이스 찾다가 포기하고 답봤는데 바텀업 재귀 써서 푸는 문제였다.

 

답보고 생각해보니까 각 단계에 대해서 이전 단계는 (-1, -1)과 (-1, 0), (0, -1) + right[0] 세가지이므로

 

바텀업 재귀가 맞는 풀이였다. 왜 n*n포문으로 했는지 나도 모르겠다. 심지어 그렇게 푼 코드 코너케이스를 하나도 못찾아서 포기하고 정답찾아봄..

 

같은 티어여도 정올 출처 문제들은 훨씬 어려운거 같다..

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
int n;
int l[2005];
int r[2005];
int dp[2005][2005]; // 왼쪽 = 1 오른쪽 2일때 최적값

int cg(int lc, int rc) {
	if (lc >= n + 1 || rc >= n + 1) return dp[lc][rc] = 0;
	if (dp[lc][rc] != -1) return dp[lc][rc];
	int s3 = -1;
	if (l[lc] > r[rc]) s3 = cg(lc, rc + 1) + r[rc];
	int s1 = cg(lc + 1, rc);
	int s2 = cg(lc + 1, rc + 1);
	dp[lc][rc] = max({ s1, s2, s3 });
	return dp[lc][rc];
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", l + i);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%d", r + i);
	}
	for (int i = 0; i <= n + 1; i++) {
		for (int j = 0; j <= n + 1; j++) {
			dp[i][j] = -1;
		}
	}

	cout << cg(1, 1);

	return 0;
}

/*int main()
//{
//    int n;
//    scanf("%d", &n);
//    for (int i = 1; i <= n; i++) {
//        scanf("%d", &l[i]);
//    }
//    for (int i = 1; i <= n; i++) {
//        scanf("%d", &r[i]);
//    }
//    for (int i = 0; i <= n; i++) {
//        for (int j = 0; j <= n; j++) {
//            dp[i][j] = -1;
//        }
//    }
//    int mx = 0;
//    /*for (int i = 1; i <= n; i++) {
//        for (int j = 1; j <= n; j++) {
//            int s1 = dp[i - 1][j];
//            int s2 = dp[i - 1][j - 1];
//            int s3 = -1;
//            if (l[i] > r[j]) {
//                s3 = dp[i][j - 1] + r[j];
//            }
//            dp[i][j] = max({ s1, s2, s3 });
//            if (dp[i][j] > mx && (i == n || j == n) ) mx = dp[i][j];
//            if (dp[i - 1][j] == -1 && l[i] <= r[j]) break;            
//        }
//    }
//    dp[0][0] = 0;
//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < n; j++) {
//            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j]);
//            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
//            if (l[i + 1] > r[j + 1]) {
//                dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + r[j + 1]);
//            }
//            
//        }
//    }
//    for (int i = 0; i <= n; i++) {      
//        if (dp[i][n] > mx) {
//            mx = dp[i][n];
//        }
//        if (dp[n][i] > mx) {
//            mx = dp[n][i];
//        }
//    }
//
//    /*for (int i = 0; i <= n; i++) {
//        for (int j = 0; j <= n; j++) {
//            cout << dp[i][j] << " ";
//        }
//        cout << "\n";
//    }
//    
//    cout << mx;
//    return 0;
//}*/