문제

이 문제는 점화식으로 풀면 너무 좋은 문제이지만, 그렇게 풀지 않는다면 정말 고통속에서 코드를 짜게 될 수도 있다.

문제 링크

문제 접근

  • 처음에 이문제를 평소 푸는 것 처럼 점화식을 이용하지 않고 풀려고 했다.
  • 하지만 이와 같이 규칙이 딱딱 정해져 있는 경우에는 점화식을 이용하는 것이 훨씬 수월하다는 것을 나중가서 깨달았다.
  • 일단 규칙 대로 코드화 하고 한번 가본 길을 또 가는 것은 낭비이기 때문에 그 길을 저장하는 용도로 디피를 사용한다.

코드

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, A[2001], B[2001], dp[2001][2001];
int find(int x, int y){
    if(x == n || y == n)return 0;
    int &ret = dp[x][y];
    if(ret != -1) return ret;
    ret = max(find(x + 1, y + 1), find(x + 1, y));
    if(A[x] > B[y])ret = max(ret, find(x, y + 1) + B[y]);
    return ret;
}
int main(){
    scanf("%d", &n);
    memset(dp, -1, sizeof(dp));
    for(int i = 0; i < n; i++)scanf("%d", &A[i]);
    for(int i = 0; i < n; i++)scanf("%d", &B[i]);
    printf("%d", find(0, 0));
}

느낀점

  • 점화식을 이용해서 dp를 푸는 방법이 유용한 때가 있다는 걸 오늘 처음 알았다!