BOJ 12932 노래방

BOJ 12932 노래방

[분류 : 다이나믹 프로그래밍]

 

[풀이]

  뭔가 간단한 문제.
  현재 p번째 노래를 누가 부를지 결정할 때 나올 수 있는 상태로 영선이가 마지막으로 부른 노래의 인덱스 i, 효빈이가 마지막으로 부른 노래의 인덱스 j가 있다.
  몇 번째 노래 해야하는 지(p)를 구할 땐 i와 j 중 큰 값에서 +1를 해주면 구할 수 있다.

 

rec(i, j) = min(rec(p, j) + "i와 p 노래 사이의 난이도", rec(i, p) + "j와 p 노래 사이의 난이도")

 

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX_N = 2e3 + 1;
int N, dp[MAX_N][MAX_N], A[MAX_N];
int rec(int a, int b) {
    if (a == N || b == N) return 0;
    int& ret = dp[a][b];
    if (ret != -1) return ret;
    int p = max(a, b) + 1;
    return ret = min(rec(p, b) + (a ? abs(A[a] - A[p]) : 0), rec(a, p) + (b ? abs(A[b] - A[p]) : 0));
}
int main() {
    memset(dp, -1, sizeof dp);
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) scanf("%d", &A[i]);
    printf("%d", rec(0, 0));
    return 0;
}