반응형
SMALL
BOJ 거리
-
12026번 BOJ 거리알고리즘 2023. 1. 23. 16:40
문제 설명 이번 문제는 B, O, J 중 한 문자로 이루어진 타일에서 아래 규칙대로 걸을 경우 필요한 에너지의 양의 최소값을 구하는 문제입니다. 보도블럭을 밟는 순서는 B, O, J, B, O, J ... 순서대로 걷게 된다. i에서 k 타일로 이동하는데 필요한 에너지는 (k-i)^2이다. 첫 번째 타일은 무조건 B이고, 마지막 타일에 무조건 도착해야 한다. (마지막 타일에 도착할 수 없을 경우 -1을 출력) 문제 풀이 아이디어 1. 우선 문제의 조건을 살펴봐야 합니다. 보도블럭의 개수가 1000개로 비교적 작은 개수이므로, N^2의 풀이법도 가능할 것으로 보입니다. 2. i번째 타일에서 i+1~N번째 타일로 넘어가는 경우를 생각할 때, 1~i번째 타일은 해당 타일까지 이동할 때 필요한 에너지의 최소값을..