백준 12026번: BOJ 거리

문제 설명

• https://www.acmicpc.net/problem/12026
• 1부터 시작해 N까지 이동해야 합니다. 이동할 때는 반드시 B->O->J 순서로 이동해야 합니다. k칸을 점프하면 k*k만큼의 에너지를 소모합니다. 1부터 N까지 에너지를 가장 적게 소모하면서 이동할때 얼마만큼의 에너지를 소모해야 하는지를 구하는 문제입니다.

접근법

• N이 1000으로 작아 2중 반복문을 사용할 수 있다고 생각했습니다.
• i번째 칸에는 i번째 위치에 도달하기까지 소모한최소 에너지를 저장합니다.

정답

import java.util.*;
import java.io.*;
import java.math.*;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		char[] arr = br.readLine().toCharArray();
		int[] dp = new int[N];
		Arrays.fill(dp, Integer.MAX_VALUE);
		dp[0] = 0;
		for (int i = 1; i < dp.length; i++) {
			for (int j = 0; j < i; j++) {
				if(arr[i] == 'O' && arr[j] == 'B' && dp[j] != Integer.MAX_VALUE) {
					dp[i] = Math.min(dp[i], dp[j] + (i-j)*(i-j));
				}
				else if(arr[i] == 'J' && arr[j] == 'O' && dp[j] != Integer.MAX_VALUE) {
					dp[i] = Math.min(dp[i], dp[j] + (i-j)*(i-j));
				}
				else if(arr[i] == 'B' && arr[j] == 'J' && dp[j] != Integer.MAX_VALUE) {
					dp[i] = Math.min(dp[i], dp[j] + (i-j)*(i-j));
				}
				
			}
		}
		System.out.println((dp[N-1]==Integer.MAX_VALUE)?-1:dp[N-1]);
	}

}