[백준 12026] BOJ 거리 [Java]

문제

http://boj.ma/12026

12026번: BOJ 거리

 

---

풀이

문제 요약

문자 ‘B’, ‘O’, ‘J’로만 이루어진 문자열에서 규칙을 준수하며 문자열의 처음부터 끝까지 이동하기 위한 최소 비용을 계산하자.

아이디어

문자열의 길이가 최대 1e3이므로 $O(N^2)$으로 풀이할 수 있다.

점화식은 다음과 같다.

dp[i] : i번째 보도 블록에 이동하기 위한 최소 에너지 양(도달하지 못하면 -1)

i - 1 ~ 0번 블록 중 i번 보도 블록으로 점프할 수 있다면, 이전 블록 + 거리의 제곱의 값과, dp[i]를 비교해 최솟값을 저장하면 된다.

        // Solve
        if (A[0] != 'B') {
            System.out.println(-1);
            return;
        }

        int[] dp = new int[N];
        final int MAX = (int) 1e10;
        Arrays.fill(dp, MAX);
        dp[0] = 0;
        for (int i = 1; i < N; ++i) {
            for (int j = 0; j < i; ++j) {
                if (A[i] == 'B' && A[j] == 'J'
                || A[i] == 'O' && A[j] == 'B'
                || A[i] == 'J' && A[j] == 'O') {
                    dp[i] = (int) Math.min(dp[i], dp[j] + Math.pow(j - i, 2));
                }
            }
        }
        
        // Output
        System.out.println(dp[N - 1] == MAX ? -1 : dp[N - 1]);

풀이 시간

10분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/12026.java

problem-solving/baekjoon-online-judge/easy/12026.java at main · rogi-rogi/problem-solving