[백준] 12026 BOJ 거리 - JAVA

1. 문제 유형 : DP

2. 시간복잡도 : O(N^2) 

 

현재 i를 기준으로 이전에서부터 올 수 있는 부분(j)을 찾는다. (이전 알파벳)

dp[i] = min(dp[i], dp[j] + (i-j)*(i-j))

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	static final int INF = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());
		int dp[] = new int[N];
		int[] chs = new int[N];
		char[] spt = in.readLine().toCharArray();
		for (int i = 0; i < N; i++) {
			if(spt[i] == 'B') chs[i] = 0;
			if(spt[i] == 'O') chs[i] = 1;
			if(spt[i] == 'J') chs[i] = 2;
		}
		Arrays.fill(dp, INF);
		dp[0] = 0;
		for (int i = 0; i < N; i++) {
			// 이전 알파벳 찾기
			// B : 0  O : 1  J : 2  이전의 알파벳 : (본인+2)%3
			for (int j = i-1; j >= 0; j--) {
				if((chs[j] == (chs[i]+2) % 3) && dp[j] != INF) {
					dp[i] = Math.min(dp[i], dp[j] + (i-j)*(i-j));
				}
			}
		}
		System.out.println(dp[N-1] == INF ? -1 : dp[N-1]);
	}

}