와이유스토리

[DP(Top-Down)] 백준 10835 카드게임 C++ 본문

코딩테스트/동적계획법

[DP(Top-Down)] 백준 10835 카드게임 C++

유(YOO) 2023. 9. 4. 16:26

10835번: 카드게임 (acmicpc.net)

 

10835번: 카드게임

첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오

www.acmicpc.net

 

#include <iostream>
#include <vector>
#define N 2001

using namespace std;

int n;
vector<int> l(N, 0);
vector<int> r(N, 0);
int dp[N][N];

int func(int s, int e) {
    int& ret = dp[s][e];
    if (ret != -1) return ret;
    if ((s >= n) || (e >= n)) return 0;

    ret = 0;
    if (l[s] > r[e]) ret = max(max(func(s+1, e), func(s+1, e+1)), func(s, e+1) + r[e]);
    else ret = max(func(s+1, e), func(s+1, e+1));

    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n;

    for(int i=0; i<n; i++) cin >> l[i];
    for(int i=0; i<n; i++) cin >> r[i];

    fill(&dp[0][0], &dp[N-1][N], -1);
    cout << func(0, 0);

    return 0;
}

'코딩테스트 > 동적계획법' 카테고리의 다른 글

[DP(Top-Down)]백준 1937 욕심쟁이 판다 C++  (0) 2023.09.04
[DP(Top-Down)] 백준 2565 전깃줄 C++  (0) 2023.09.03
[누적합] 프로그래머스 파괴되지 않은 건물 C++  (0) 2023.02.12
[누적합] 백준 11660 구간 합 구하기 5 C++  (0) 2022.02.09
[누적합] 백준 11659 구간 합 구하기 4 C++  (0) 2022.02.09
'코딩테스트/동적계획법' Related Articles more
Comments