12026 BOJ 거리

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

d[i] = i까지 오는데 필요한 에너지 양의 최소값 이라고 하자. 매번 0~i-1까지 검사하면서 현재 알파벳 이전에 올 수 있는 알파벳을 찾아서 최소값을 갱신한다. O(N^2)으로 해결할 수 있다.

#include <cstdio>
#include <algorithm>
#define INF 987654321
using namespace std;
 
int main()
{
    int n,d[1005];
    char s[1005];
    scanf("%d %s",&n,s);
    fill_n(d,1005,INF);
    d[0]=0;
    for(int i=1;i<n;i++) for(int j=0;j<i;j++)
        if((s[i]=='B' && s[j]=='J') || (s[i]=='O' && s[j]=='B') || (s[i]=='J' && s[j]=='O'))
            d[i]=min(d[i],d[j]+(i-j)*(i-j));
    printf("%d",d[n-1]!=INF?d[n-1]:-1);
    return 0;
}