[BAEKJOON] 10835 카드게임

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <algorithm> using namespace std; //시간초과..... //초기화는 무조건 -1 int n; vector<vector<int>>Card(2, vector<int>(2001)); vector<vector<long long>>DP(2001, vector<long long>(2001, -1)); long long Game(int left,int right) { if (left == n || right == n) return 0; long long &ret = DP[left][right]; if (ret != -1) return ret; int num1 = 0, num2 = 0, num3 = 0; num1 = Game(left + 1, right); num2 = Game(left + 1, right + 1); if(Card[0][left]>Card[1][right]) num3 = Game(left, right + 1)+Card[1][right]; return ret = max(num1, max(num2, num3)); } int main() { scanf("%d", &n); for (int j = 0; j < n; j++) scanf("%d", &Card[0][j]); for (int j = 0; j < n; j++) scanf("%d", &Card[1][j]); printf("%lld",Game(0, 0)); return 0; }

한번은 시간초과

초기화는 무조건 -1로!!!!

왜냐하면 답이 0이 나올 수 도 있기 때문에 그 경우마다 모두 돌아주면 시간이 오래 걸리기 때문이다!!!!