이번 문제는 다이나믹 프로그래밍을 통해 해결하였다. 문자열을 순회하며 현재 이전의 문자들 중 바로 이전에 올 수 있는 문자의 인덱스를 찾아 문제에서 주어진 연산을 통해 도출되는 값 중 가장 작은 것을 dp[현재]로 갱신하는 방식으로 접근하였다. 이를 위해 dp배열은 sys.maxsize를 통해 min함수에 걸러지도록 설정하였고 이전 문자를 찾기위해 함수를 따로 작성하여 사용했다.

점화식은 dp[n]=min(dp[n], dp[m]+(n-m]\*\*2)을 사용하였다.

• n을 입력받는다.
• 보도블럭을 나타내는 문자열 block을 입력받는다.
• dp배열을 0 뒤에 maxsize n개를 넣어 선언한다.
• 이전 단어를 반환하는 함수 prev_word를 매개변수 s와 함께 선언한다.
  -> 만약 s가 B라면 J를 반환한다.
  -> 만약 s가 O라면 B를 반환한다.
  -> 만약 s가 J라면 O를 반환한다.
• 1부터 n-1까지 반복하는 i에 대한 for문을 돌린다.
  -> 이전 문자를 저장하는 임시 변수 prev를 선언하고 prev_word(block[i])를 저장한다.
  -> i번 반복하는 j에 대한 for문을 돌린다.
  --> 만약 block[j]가 prev와 같다면 dp[i]를 dp[i]와 dp[j]+(i-j)**2 중 더 작은 값으로 갱신한다.
• 만약 dp[n-1]이 maxsize라면 (갱신되지 않았다면) -1을 출력한다.
• 그 외에는 dp[n-1]을 출력한다.

Code

import sys
n=int(input())
block=str(input())
dp=[0]+[sys.maxsize]*n
def prev_word(s):
    if s=='B':
        return 'J'
    if s=='O':
        return 'B'
    if s=='J':
        return 'O'

for i in range(1, n):
    prev=prev_word(block[i])
    for j in range(i):
        if block[j]==prev:
            dp[i]=min(dp[i], dp[j]+(i-j)**2)
if dp[n-1]==sys.maxsize:
    print(-1)
else:
    print(dp[n-1])