#12026

#12026

문제

풀이

• B->O->J 순으로 진행되어야 함을 인지하고
• 끝나는 지점(링크)는 꼭 J로 끝날 필요는 없다. (순서만 맞게 하면 됨)

N=int(input())
l=list(map(str,input()))

dp=[10000000001]*N
dp[0]=0

for i in range(N):
    now=l[i]
    right=''
    if now == 'B':
        right='O'
    elif now =='O':
        right='J'
    else:
        right='B'

    for j in range(i+1,N):
        if l[j]==right:
            dp[j]=min(dp[j],dp[i]+(j-i)*(j-i))
ans=dp[N-1]
if ans==10000000001:
    print(-1)
else:
    print(ans)

• 현재가 B라면 뒤에 와야하는 문자는 O이다.
• dp[j]의 경우 l이 j까지 오는데 사용되는 비용이다.
  원래의 dp[j]와 (j-i)의 제곱을 더한 값을 비교해 최소값을 dp[j]에 넣도록 한다.
• 비용은 dp[N-1]로 이 값이 10000000001이라면 l이 BOJ의 순대로 진행되지 않았기에 -1을 출력하고 아니라면 N-1까지 오는데 비용인 dp[N-1]을 출력한다.

참고