12026번: BOJ 거리

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


$O(n^2)$

dp[i]=min(j<i && j->i 가능)(dp[j]+(i-j)*(i-j))

#include<cstdio>
int n, dp[1000];
char s[1001];
int main() {
    scanf("%d%s", &n, s);
    for (int i = 1; i < n; i++) {
        dp[i] = 1e9;
        for (int j = 0; j < i; j++)
            if ((s[j] == 'B'&&s[i] == 'O' || s[j] == 'O'&&s[i] == 'J' || s[j] == 'J'&&s[i] == 'B') && dp[j] + (i - j)*(i - j) < dp[i])
                dp[i] = dp[j] + (i - j)*(i - j);
    }
    printf("%d", dp[n - 1] ^ (int)1e9 ? dp[n - 1] : -1);
    return 0;
}