문제

https://www.acmicpc.net/problem/12026

---

입력

첫째 줄에 N 이 주어진다.
둘째 줄에는 보도블록에 쓰여 있는 글자가 1번부터 순서대로 주어진다.

---

출력

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

---

풀이

제한조건

• 1 ≤ N ≤ 1,000

접근방법

DP
문제가 작은 문제로 부터 큰 문제의 정답을 찾는 것이며
구하고자 하는 값이 최솟값/최댓값과 같은 형태의 문제이다.

위 두 단서로 부터 DP임을 알아낼 수 있다.

- X칸으로 가기 위한 에너지 = X-1칸으로 가기 위한 에너지 + 1칸을 움직이기 위한 에너지.
- X칸으로 가기 위한 에너지 = X-2칸으로 가기 위한 에너지 + 2칸을 움직이기 위한 에너지.
- X-1칸으로 가기 위한 에너지 = X-2칸으로 가기 위한 에너지 + 1칸을 움직이기 위한 에너지.

즉 cost[X] = cost[X-n] + n칸 이동 비용 이라는 것을 알 수 있다.

이제 문제에서 주의할 점을 보자.
스타트는 B -> O -> J -> B ... 의 순으로 이동한다.
따라서 X-n칸으로 이동할 때, 현재의 보도블록 글자에 따라 이전 블록을 걸러내면 된다.

이때 if문을 덕지덕지 붙여서 작성하는 방법도 있지만,

if(str[i] == 'B' && str[j] == 'J'){
	...
} else if...

-> 너무 복잡한 코드

간단하게 Map을 선언하여 이전 글자를 기록해 두자.

//Map<현재글자, 이전글자>
if (str[j] == map.get(str[i])){
	...
}

이제 위의 점화식을 코드로 옮기자.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = stoi(in.readLine());
		char[] str = in.readLine().toCharArray();

		Map<Character, Character> map = new HashMap<>();
		map.put('B', 'J');
		map.put('O', 'B');
		map.put('J', 'O');

		int[] cost = new int[N];
		Arrays.fill(cost, 987654321);
		cost[0] = 0;

		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < i; ++j) {
				if (str[j] == map.get(str[i]))
					cost[i] = Math.min(cost[i], cost[j] + ((i - j) * (i - j)));
			}
		}
		System.out.println(cost[N - 1] == 987654321 ? -1 : cost[N - 1]);
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}