BOJ 11570번 환상의 듀엣

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

N <= 2000

10^6 이하인 N개의 음이 주어지고 이 N개의 음을 두 사람이 나누어 부른다.

음을 나누어 순서대로 놓았을 때

ai 를 A가 i번째로 낸 음이라고하면 |\(a_i - a_{i-1}\)| 가 ai 를 낼 때의 힘든 정도이다.

A와 B의 힘든 정도의 합을 최소로 하도록 음을 나누었을 때의 합을 구하는 문제이다.

C[i] : i번째 음

go(pos, lastA, lastB) = pos 번째 음표부터 보며, A사람의 마지막 음이 lastA, B사람의 마지막 음이 lastB 일때 최소값

pos 번째 음을 A가 낼 경우 go(pos+1, pos, lastB) + abs(C[pos] - C[lastA]) 이고

pos 번째 음을 B가 낼 경우 go(pos+1, lastA, pos) + abs(C[pos] - C[lastB]) 이다.

그런데 이렇게하면 O(N^3) 이다.

(lastA와 lastB를 실제 음의 값이아닌 음의 위치를 저장하여 최대 10^6이아니라 2000이 되도록 한것에 주목하자)

그렇기 때문에 시간초과이다. 그런데 조금만 관찰해 보면 pos 번째 음을 A가 내던 B가 내던 

pos 번째 음을 내야 할 때에 lastA 와 lastB 둘 중하나는 무조건 pos-1 이라는 것을 알 수가 있다.

왜냐하면 바로 직전에 A던 B던 누군가가 음을 냈을 것이기 때문이다.

이 사실을 이용하면 한명은 무조건 pos-1 을 마지막으로 냈다는 사실을 알 수가 있기 때문에 바로 직전에 내지않은 사람의

음만 가지고 있으면 된다. 즉,

go(pos, last) : pos 번째 음부터 내야하며, 직전 음을 낸 사람이 아닌 사람이 마지막으로 낸 음이 last 일 때 최소합

이렇게 되면 두가지 경우로 나뉜다. 'pos 번째 음을 직전 음을 낸사람이 또 내는 경우' 와 '직전 음을 내지 않은 사람이

내는 경우' 이렇게 두가지 이다. 

첫번째 경우에는 go(pos+1, last) + abs(C[pos] - C[pos-1]) 가 되고

두번째 경우에는 go(pos+1, pos-1) + abs(C[pos] - C[last]) 가 된다.

그리하여 O(N^2) 에 풀 수가 있게 된다.

근데 부분문제 테이블을 계산하는 순서가 뒤죽박죽이라 비재귀로 구현하는건 생각안해봤고 그냥 재귀로했는데

비재귀로 구현한 사람도 있었다. 귀찮으므로 나중에 생각해봐야겠다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
int N;
int A[2000];
int dp[2000][2001];
int go(int i, int j){
    if(i == N) return 0;
    int& cache = dp[i][j+1];
    if(cache != -1) return cache;
    cache = min(cache, go(i+1,j) + (!i ? 0 : abs(A[i] - A[i-1])));
    cache = min(cache, go(i+1,i-1) + (j<0 ? 0 : abs(A[i] - A[j])));
    return cache;
}
int main() {
    memset(dp,-1,sizeof(dp));
    cin >> N;
    for(int i = 0 ; i < N; i++) cin >> A[i];
    cout << go(0,-1);
    return 0;
}