BOJ 11570 : 환상의 듀엣

https://www.acmicpc.net/problem/11570

11570번: 환상의 듀엣

 

난이도(객관적): Platinum V

난이도(개인적): Gold I (BOJ 2618 하위호환)

 

문제 난이도도 환상인 문제이다. 이 문제는 dp를 사용하여 풀 수 있는데, dp 테이블을 다음과 같이 나타내면 된다.

• dp[i][j] = 상덕이가 현재 i번째 인덱스, 희원이가 j번째 인덱스에 있을 때 드는 힘의 최솟값

 

일 때, dp[i][j] = min( dp[i][max(i, j) + 1] + 희원 거리 , dp[max(i, j) + 1][j] + 상덕 거리 ) 이 성립한다.

처음 시작할 때는 지금 있는 위치를 정의할 수 없다는 것을 유의한다.

 

#include <iostream>
#include <math.h>

using namespace std;
#define MAXN 2001
#define INF 2147483000

int N;
int arr[MAXN];
int dp[MAXN][MAXN]; // 1. 상덕 2. 희원

int solve(int l, int r) {

    if (l >= N || r >= N) return 0;

    int& cache = dp[l][r];
    if (cache != -1) return cache;

    int nxt = max(l, r) + 1;
    int sangduk = l != 0 ? abs(arr[l] - arr[nxt]) : 0;
    int hweewon = r != 0 ? abs(arr[r] - arr[nxt]) : 0;

    int ans = min(solve(l, nxt) + hweewon, solve(nxt, r) + sangduk);

    return cache = ans;
}

int main() {

    cin >> N;
    for (int i = 1; i <= N; i++) cin >> arr[i];
    for (int i = 0; i <= N; i++) for (int j = 0; j <= N; j++) dp[i][j] = -1;

    cout << solve(0, 0) << endl;
}