백준 12026. BOJ 거리

tose33 2022. 7. 11. 13:50

12026번: BOJ 거리

스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 출력한다. 만약, 스타트가 링크를 만날 수 없는 경우에는 -1을 출력한다.

www.acmicpc.net

dp 문제.

d[i] : i번째 칸에 도달하는데 드는 최소 비용.

현재 칸의 알파벳에 따라 이전 칸에서 현재칸까지 오는 최소비용을 구해주면 된다.

예를들어 현재 칸이 'O'라면 'O'에 도달하기 전 칸은 'B' 칸 이었을 것이므로 이전 칸들 중 'B' 칸인 곳을 찾고, 해당 'B' 칸에 도달하는 최소비용 + (두 칸의 거리)^2 를 구해서 현재 최소 비용중 작은 값으로 갱신하면 된다.

문제를 풀때 변수이름 하나를 BOJ라고 뒀는데 컴파일 에러가 났다.

아마 백준 채점 시스템에 BOJ라는 변수명을 사용중인듯 하다.