12026번 - BOJ 거리(DP)

문제:

BOJ 거리는 보도블록 N개가 일렬로 놓여진 형태의 도로이다. 도로의 보도블록은 1번부터 N번까지 번호가 매겨져 있다.

스타트의 집은 1번에 있고, 링크의 집은 N번에 있다. 스타트는 링크를 만나기 위해서 점프해가려고 한다.

한 번 k칸 만큼 점프를 하는데 필요한 에너지의 양은 k*k이다.

스타트는 BOJ를 외치면서 링크를 만나러 가려고 한다. 따라서, 스타트는 B, O, J, B, O, J, B, O, J, ... 순서로 보도블록을 밟으면서 점프를 할 것이다.

스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 1 ≤ N ≤ 1,000이 주어진다.

둘째 줄에는 보도블록에 쓰여 있는 글자가 1번부터 순서대로 주어진다.

스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 출력한다. 만약, 스타트가 링크를 만날 수 없는 경우에는 -1을 출력한다.

 

풀이:

내가 풀고 난 이후, 뭔가 더 깔끔한 풀이가 있을 것 같아서, 구글링을 한번 해봤고, 아래 블로그를 찾아냈다.

백준 12026번: BOJ 거리 (velog.io)

보고나서 나는 참 어렵게 풀었구나 라고 생각했다.

코드는 아래와 같다.

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

public class BOJ거리_12026번_best {
    public static void main(String[] args) throws IOException {
        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]);
    }
}

1. 먼저 입력을 받아준다. arr[]에 'B', 'O', 'J'를 입력받은 순서대로 저장한다.
2. dp를 Integer.MAX_VALUE로 초기화한다. dp[0]만 0으로 초기화 해준다.
3. i = 1부터 dp.length 즉, N만큼 아래 과정을 반복해준다.
   1. j = 0~ i까지 아래 과정을 반복해준다. 
      1. arr[i]가 O이고 arr[j]에 있는 문자가 B일때, dp[i] = Math.min(dp[i], dp[j] + (i-j)*(i-j))이다.
         이때, dp[j]가 Integer.MAX_VALUE라면, 수행해주지 않아도 된다.
         어짜피 j에는 도달할 수 없기 때문이다.
      2. arr[i]가 J이고 arr[j]에 있는 문자가 O일때 1번과 같은 방법을 취해준다.
      3. arr[i]가 B이고 arr[j]에 있는 문자가 J일때 1번과 같은 방법을 취해준다.
4. dp[N-1]에 Integer.MAX_VALUE가 저장되어 있다면, 목적지까지 갈 수 없다. -1을 출력해준다.
   그렇지 않다면 dp[N-1]을 출력해준다.

 

시행착오:

처음에는 올바른 풀이와 같이 생각했다.

하지만 모든 요소를 하나하나 확인하기 싫었다.

100을 50과 50으로 나눠보면 각 거리의 제곱의 합이 2500 + 2500 = 5000이 나온다.

100을 49와 51로 나누면 각 거리의 제곱의 합이 5002가 나온다.

어느 수를 두 수로 나눌때, 중간에서 멀어질수록 제곱의 합이 커지는 결과가 나온다는 뜻이다.

그렇게, 만일 제곱의 합이 이전 값보다 증가한다면, for문을 중단시켜 주려고 했다.

제곱의 합이 증가했다는 뜻은 중간에서 멀어졌다는 의미이기 때문이다.

 

하지만 결국 틀렸다.

생각해보니, 막대기를 2번 자르는게 아니라 여러번 잘라줄 때, dp를 이용해 각각 비교하지 않으면 알 방법이 없다.

그래서 포기하고 모든 요소를 하나하나 확인해주기로 했고,

이전 풀이의 영향을 받은 결과 아래와 같은 풀이가 나왔다.

 

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

public class BOJ거리_12026번 {
    static int N;
    static long[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        dp = new long[N];
        List<Integer> bList = new ArrayList<>();
        List<Integer> oList = new ArrayList<>();
        List<Integer> jList = new ArrayList<>();

        char[] chars = br.readLine().toCharArray();
        char first = chars[0];
        if (first == 'B') {
            bList.add(0);
        } else {
            System.out.println(-1);
            System.exit(0);
        }

        for (int i = 1; i < N; i++) {
            char c = chars[i];
            if (c == 'B') {
                dp[i] = findMin(bList, jList, i);
            } else if (c == 'O') {
                dp[i] = findMin(oList, bList, i);
            } else if (c == 'J') {
                dp[i] = findMin(jList, oList, i);
            }
        }

        System.out.println(dp[N-1]);
    }

    static long findMin(List<Integer> now, List<Integer> before, int i) {
        long min = -1;
        if (!before.isEmpty()) {
            now.add(i);
            int size = before.size();
            min = dp[before.get(size-1)]
                    + (long)(i - before.get(size - 1)) * (i - before.get(size-1));
            for (int j = before.size()-2; j >= 0 ; j--) {
                long temp = dp[before.get(j)] + (long)(i - before.get(j)) * (i - before.get(j));
                if (min > temp) {
                    min = temp;
                }
            }
        }
        return min;
    }
}

N의 제곱의 최대값이 1000 x 1000이므로 범위로 long이 아닌 int로 충분히 가능하다.

빨리 푸는 것도 중요하지만, 이전 과정을 과감하게 버리는 것도 중요하다는 것을 느꼈다.