백준 12026 번 : BOJ 거리 풀이(Java) - DP

 www.acmicpc.net/problem/12026

12026번: BOJ 거리

 

Solution

1. 이 문제는 N 이 최대 1000 밖에 안된다. 별로 크지 않다는 의미이고, 시간 제한도 2초로 굉장히 널널하다. 그래서 2중 for문을 돌아도 되겠다는 생각이 들었다. 처음에는 DP에 2중 for 문을 쓰면 터지지 않을까.. 걱정했지만 104ms 라는 만족스러운 시간으로 통과했다. 역시 먼저 드는 생각으로 풀어보는 게 최고인 것 같다.

 

2. 이 문제에는 규칙이 있다.

B 를 밟았다면, 다음은 무조건 O를, 마찬가지로

O -> J

J -> B

 

를 밟아야 한다.

 

9

BOJBOJBOJ

가 입력이라 가정해보자. 

맨 처음(0번)은 무조건 B 이므로, 다음 순번인 1번부터 끝까지 살피면서 O인 곳을 체크한다. 갈 수 있는 모든 곳을 체크하면서, 인덱스 0번 -> 인덱스 i 번으로 가는 데 드는 비용은 i*i 가 될 것이다. 

 

그 다음인 1번은 O 이므로, 다음 순번인 2번부터 끝까지 살피면서 J인 곳을 체크한다. ( B -> O -> J -> B -> ... )

마찬가지로 (i - 1) * (i - 1) 을 비용으로 정해준다.

 

2번인 J 도 똑같은 과정을 했다고 생각하면,

 

0번의 B에 의해서, 1번의 O, 4번의 O, 7번의 O 가 값이 정해졌고,

1번의 O에 의해서, 2번의 J, 5번의 J, 8번의 J 의 값이 정해졌고,

2번의 J 에 의해서, 3번의 B, 6번의 B 의 값이 정해졌다.

 

도착하는 기준은, dp[N-1] 의 값(0 번부터 N번 까지 가는 데 드는 최소 비용) 이 초기화된 값( 최소 값을 구하는 것이므로, 아주 큰 값(Integer.MAX_VALUE 라던가) ) 이 아니라면 N번에 갈 수 있다는 것이 된다.

 

그러므로 출력 형식은, dp[N-1] 이 MAX 라면 -1 을 출력, 아니라면 dp[N-1] 을 출력하면 된다.

 

3. 하지만 2번처럼 그 때마다 값을 그냥 바꿔주면 최소가 보장되지 않는다.

0번                k번            i번               N-1번

B                   O              O                 J

 

 라면, k번과 i 번 중 어느 O를 밟고 가야 최선일까?

0~k-1, k+1 ~ i - 1 번에 있는 것들이 어떻게 될 지 모르니까,

만약 a -> b 로 간다면,

• dp[b] 배열에 담겨있는 값과, ( 0번부터 b 번까지 가는 값들 중 현재까지 발견된 최소 값)
• dp[a] + (b-a)^2 의 값 (0번부터 a 번까지 가는 최소값 + a 번에서 b 번까지 점프하는데 드는 비용 )

을 비교해서, 작은 값으로 담아줘야 한다.

이 점만 알면 구현은 쉽다.

 

Source Code

import java.io.*;
import java.util.Arrays;

public class Main {
    private static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    private static final int MAX = 987654321;
    private static int N;
    private static char[] street;
    private static int[] dp;
    private static void input() throws IOException {
        N = Integer.parseInt(bufferedReader.readLine());
        street = new char[N];
        street = bufferedReader.readLine().toCharArray();
        dp = new int[N];
        Arrays.fill(dp, MAX);
    }

    private static void solve() throws IOException {
        dp[0] = 0;
        for(int i = 0; i < N-1; i++) {
            int now = i;
            char nowBlock = street[now];
            if(nowBlock == 'B') {
                for(int j = i +1; j < N; j++) {
                    int next = j;
                    char nextBlock = street[next];
                    if(nextBlock == 'O') {
                        dp[next] = Math.min(dp[next], dp[now] + (next-now) * (next-now));
                    }
                }
            } else if(nowBlock == 'O') {
                for(int j = i +1; j < N; j++) {
                    int next = j;
                    char nextBlock = street[next];
                    if(nextBlock == 'J') {
                        dp[next] = Math.min(dp[next], dp[now] + (next-now) * (next-now));
                    }
                }
            } else {
                for(int j = i +1; j < N; j++) {
                    int next = j;
                    char nextBlock = street[next];
                    if(nextBlock == 'B') {
                        dp[next] = Math.min(dp[next], dp[now] + (next-now) * (next-now));
                    }
                }
            }
        }
        if(dp[N-1] == MAX) {
            System.out.println("-1\n");
        } else {
            System.out.println(dp[N-1]);
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
}