https://www.acmicpc.net/problem/10835
1. 왼쪽 카드만 버리는 경우
2. 왼쪽 카드와 오른쪽 카드를 버리는 경우
3. "왼쪽 카드 < 오른쪽 카드" 를 만족하여 오른쪽 카드만 버리는 경우
이 세가지 경우를 모두 고려해주어야 한다.
dp[left][right] 는 왼쪽 카드와 오른쪽 카드를 left장, right장 버렸을 때 점수의 최댓값이다.
코드는 다음과 같다.
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int dp[2001][2001];
int leftCard[2001];
int rightCard[2001];
int solve(int left, int right){
if(left >= n || right >= n) return 0;
if(dp[left][right] != -1) return dp[left][right];
dp[left][right] = max(solve(left+1,right+1), solve(left+1,right));
if(leftCard[left] > rightCard[right]){
dp[left][right] = max(dp[left][right], solve(left,right+1)+rightCard[right]);
}
return dp[left][right];
}
int main(){
ios_base :: sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
fill(&dp[0][0],&dp[2000][2001],-1);
cin >> n;
for(int i = 0; i < n; i++){
cin >> leftCard[i];
}
for(int i = 0; i < n; i++){
cin >> rightCard[i];
}
cout << solve(0,0);
}
2차원 배열을 (0,0)부터 (n,n)까지 초기화 할때 fill(&arr[0][0],&arr[n-1][n], value)의 형식으로 써주면 value 값으로 초기화 할 수 있다.
아직 dp를 보면 피보나치 수열만 생각나고 dp의 개념이 잡히지 않았다면, 재귀로 dp문제를 푸는 것을 추천한다. 재귀 함수 부분을 통해 규칙을 그대로 써 나가면 된다. 처음에 dp문제를 접하면 어떻게 접근해야할지가 고민인 경우가 많은데 위와 같이 짜니 코드를 이해하기 쉽고 접근도 감이 잡힐 거 같다.(물론 나도 아직 Dp가 뭔지 잘 모르겠다..)
'📚알고리즘 > 백준' 카테고리의 다른 글
[백준 27650번] 마법박스 (C++) (2) | 2024.03.25 |
---|---|
[백준 20500번] Ezreal 여눈부터 가네 ㅈㅈ (C++) (0) | 2023.11.04 |
[백준 14728번] 벼락치기 (C++) (1) | 2023.11.01 |
[백준 9764번] 서로 다른 자연수의 합 (C++) (1) | 2023.10.31 |
[백준 3067번] Coins (C++) (1) | 2023.10.29 |