[백준] 온라인 저지 12026번 : BOJ 거리(Java), DP

DP 문제로 점화식을 세운 후 진행한다.

점화식을 세우는데 시간이 좀 걸렸다..

 

 

 

DP[n] : n까지 이동하는데 걸리는 에너지의 최솟값이라고 하자.

현재 위치에서 다음 위치로 갈 수 있는 경우의 수를 탐색하며(B -> O -> J 순서) 탐색할 수 있는 경우, 점화식은 다음과 같다.

// i : 현재 위치
// j : 다음 위치
dp[j] = Math.min(dp[j], dp[i] + (j-i)*(j-i));

 

 

 

문제 풀이

import java.util.*;

public class P026_BOJ거리구하기 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String str = sc.next();
        int answer = 0;

        int[] dp = new int[N];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for(int i=0; i<N; i++) {
            char nowChar = str.charAt(i);
            System.out.println("i: " + i);
            for(int j=i+1; j<N; j++) {
                char nextChar = str.charAt(j);
                if((nowChar == 'B' && nextChar == 'O') || (nowChar == 'O' && nextChar == 'J') || (nowChar == 'J' && nextChar == 'B')) {
                    if(dp[i] != Integer.MAX_VALUE) { // 오버플로우 방지
                        dp[j] = Math.min(dp[j], dp[i] + (j-i)*(j-i));
                        System.out.println("j: " + j + ", dp[j]: " + dp[j]);

                    }
                }
            }
        }

        if(dp[N-1] == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(dp[N-1]);
        }
    }
}