Jae-Kyung Cho LLM Developers who was a Robotics engineer

Baekjoon-12026-BOJ 거리

시간 제한이 2초, N의 최대값이 1이므로 O(N^2) 으로도 충분히 풀 수 있다.

import sys
input = sys.stdin.readline

N = int(input())
chars = input().strip()
infty = int(1e6)

dp = [infty for _ in range(N)]
dp[0] = 0
for i in range(N-1):
    for j in range(i+1,N):
        if chars[i] == 'B':
            if chars[j] == 'O':
                dp[j] = min((j-i)**2+dp[i], dp[j])
        if chars[i] == 'O':
            if chars[j] == 'J':
                dp[j] = min((j-i)**2+dp[i], dp[j])
        if chars[i] == 'J':
            if chars[j] == 'B':
                dp[j] = min((j-i)**2+dp[i], dp[j])

if dp[N-1] == infty:
    print(-1)
else:
    print(dp[N-1])
Comments