BOJ거리 실버1 (백준, DP)

N = int(input())
road = list(input())
dp = [float('inf')] * N
dp[0] = 0
for i in range(1, N):
  for j in range(i):
    sig = 0
    if road[i] == 'B' and road[j] == 'J':
      dp[i] = min(dp[i], dp[j]+(i-j)**2)
    if road[i] == 'O' and road[j] == 'B':
      dp[i] = min(dp[i], dp[j]+(i-j)**2)
    if road[i] == 'J' and road[j] == 'O':
      dp[i] = min(dp[i], dp[j]+(i-j)**2)

if dp[-1] != float('inf'):
  print(dp[-1])
else:
  print(-1)

 

이 문제를 알게 된 게 행운이라고 생각한다.

 

반복되는 문자의 형태를 규칙으로 하는 경우, 뒤에 오는 정해진 값이 존재할때 자신의 값과 전의 값에 규칙을 적용한 값을 더한 것 중 작은 것으로 초기화하는 테크닉을 배울 수 있었다.

 

잊지말자.