Logo냥냠감자기술 블로그
Skip to Content
AlgorithmDP (31)카드게임
작성일: 2024-01-12

문제

백준 10835 - 카드게임 

  • 난이도: 골드5
  • 알고리즘: DP

코드

#include <iostream> #include <vector> using namespace std; vector<vector<int>> cache(2000, vector<int>(2000, -1)); int n; int getMax(vector<int>& left, vector<int>& right, int leftIndex, int rightIndex) { if(leftIndex==n || rightIndex==n) { return 0; } int& ret=cache[leftIndex][rightIndex]; if(cache[leftIndex][rightIndex]!=-1) { return ret; } ret=max(ret, getMax(left, right, leftIndex+1, rightIndex)); ret=max(ret, getMax(left, right, leftIndex+1, rightIndex+1)); if(left[leftIndex]>right[rightIndex]) { ret=max(ret, getMax(left, right, leftIndex, rightIndex+1)+right[rightIndex]); } return ret; } int main() { cin>>n; vector<int> left(n); vector<int> right(n); for(int i=0; i<n; i++) { cin>>left[i]; } for(int i=0; i<n; i++) { cin>>right[i]; } cout<<getMax(left, right, 0, 0); }

회고

처음으로 vim을 이용해 코딩을 해 보았다. 처음이라 그런지 못해먹겠다… 그래도 좀더 연습해 볼 생각이다. 문제는 카드의 개수가 많지 않아 큰 고민 없이 현재 카드 더미 가장 위에 있는 카드 상태가 주어질 때 최대 점수를 저장하는 방식으로 구현하였다.