[백준 12026] BOJ 거리

https://www.acmicpc.net/problem/12026 문제이해 보도블럭 N개가 일렬로 놓여진 형태의 도로에서 스타트의 집은 1번에 있고 링크의 집은 N번에 있다. 스타트는 링크를 만나기 위해서 점프해가려고 한다.

각 보도블럭에는 B, O, J 중 하나가 쓰여있고 1번은 무조건 B이다. 항상 앞으로만 점프할 수 있고 B->O->J 순서로만 점프할 수 있다. k칸 점프를 하는데 필요한 에너지는 k^2이다.

스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 구해라. 풀이 문제를 보고 DFS로 풀려고 했으나 최악의 경우 약 333^1000의 연산이 필요하기 때문에 바로 다 른 방법을 찾아보다가 예제 4번을 직접 풀어보니 DP로 풀면 되겠다는 생각이 들었다.

코드 import sys N = int(sys.stdin.readline()) block = sys.stdin.readline() dp = [1000000] * ((len(block))-1) visit = [False]...