백준 10835 카드게임

문제 URL : https://www.acmicpc.net/problem/10835

10835번: 카드게임

문제 접근법 :

문제는 어렵지 않은문제입니다. 애초에 백트래킹으로 풀수있는문제지만 n이

2000이니 시간초과라는건 당연하겠죠 그렇다면 메모이제이션 기법을 활용해서 dp로 시간복잡도를 최소화 하라는 뜻이 분명할테니 dp로 해결하면됩니다. 

1. 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.
2. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.
3. (1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된다. 

주어진 조건1,2번 조건대로 코딩하시면됩니다.

 

소스코드 :

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

//By 콩순이냉장고 #include <bits/stdc++.h> using namespace std; #define ll long long int n; vector<int> v1, v2; vector<vector<int>> dp; void input() {     cin >> n;     v1.resize(n);     v2.resize(n);     dp = vector<vector<int>>(n, vector<int>(n, -1));     for (int i = 0; i < n; i++)         cin >> v1[i];     for (int i = 0; i < n; i++)         cin >> v2[i]; } int dfs(int l=0,int r=0) {     if (l == n || r == n) return 0;//더이상 남은카드가 없는경우     int& res = dp[l][r];     if (res != -1)return res;     int sum = 0;     sum = dfs(l + 1, r); //1번조건 왼쪽카드만 버리는경우     sum = max(sum, dfs(l + 1, r + 1));//1번조건 양쪽카드 다버리는경우     if (v1[l] > v2[r])sum = max(sum, dfs(l, r + 1) + v2[r]);//2번조건 오른쪽카드가 작을때 오른쪽카드를 버리고 그점수를 합산하는경우     return res = sum; } void solve() {     cout << dfs() << "\n"; } int main() {     ios_base::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);     //freopen("input.txt", "r", stdin);     input();     solve(); } Colored by Color Scripter

cs

 

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.