백준 10835번 카드게임

문제 링크입니다: https://www.acmicpc.net/problem/10835

재귀함수를 이용하여 간단하게 풀 수 있는 DP 문제였습니다.

조건에서 오른쪽 더미에 있는 카드가 왼쪽 더미에 있는 카드보다 작을 경우 오른쪽 더미에 있는 카드만큼 점수를 더하라고 했으므로 재귀에서 조건을 다음과 같이 두 가지 경우의 수로 나누었습니다.

1. 오른쪽 더미에 있는 카드가 왼쪽 더미에 있는 카드보다 작을 경우

a) 오른쪽 카드만큼 더하고 오른쪽 더미 인덱스를 늘린다

b) 왼쪽 카드 인덱스를 늘린다

c) 왼쪽, 오른쪽 모두 카드 인덱스를 늘린다

2. 그 외

a) 왼쪽 카드 인덱스를 늘린다

b) 왼쪽, 오른쪽 모두 카드 인덱스를 늘린다

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 2000;

 

int N;

int leftCard[MAX], rightCard[MAX];

int cache[MAX][MAX];

 

int maxScore(int leftIdx, int rightIdx)

{

        //기저 사례: 두 더미의 카드 중 하나라도 남은 카드가 없다면

        if (leftIdx >= N || rightIdx >= N)

                 return 0;

 

        int &result = cache[leftIdx][rightIdx];

        if (result != -1)

                 return result;

 

        result = 0;

        //왼쪽 덱에 있는 카드가 오른쪽에 있는 카드보다 클 경우 고려사항 3가지

        if (leftCard[leftIdx] > rightCard[rightIdx])

                 result += rightCard[rightIdx] + maxScore(leftIdx, rightIdx + 1);

        //그 외에는 고려사항 2가지

        else

                 result += max(maxScore(leftIdx + 1, rightIdx), maxScore(leftIdx + 1, rightIdx + 1));

 

        return result;

}

 

int main(void)

{

        cin >> N;

 

        for (int i = 0; i < N; i++)

                 cin >> leftCard[i];

        for (int i = 0; i < N; i++)

                 cin >> rightCard[i];

 

        memset(cache, -1, sizeof(cache));

        cout << maxScore(0, 0) << endl;

 

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~