[백준] BOJ 거리 (12026번 JAVA) / DP

[백준] BOJ 거리 (12026번 JAVA) / DP

---

[접근 방법]

스타트는 항상 B 이다.

B - > O - > J 순으로 이동하여야 한다.

DP 배열의 의미는 해당 위치 까지 "이동하는데 든 에너지의 최솟값" 이다,

 

현재 위치의 문자가 B 라면, 다음 이동 가능한 문자인 O에 대하여,

현재 위치의 문자가 O 라면, 다음 이동 가능한 문자인 J에 대하여,

현재 위치의 문자가 J 라면, 다음 이동 가능한 문자인 B에 대하여,

탐색하여 가장 적은 에너지를 소모하는 것을 DP에 저장한다.

 

1 <= i < N-1 인 정수 i , i+1 <= j < N 인 정수 j 에 대하여

DP [ j ] =  최솟값 (DP[j] , DP[i] + (j - i) * (j - i)) 로 정의 할 수 있다.

---

[JAVA 코드]

// 12026 - BOJ 거리
import java.util.*;
import java.io.*;

class Main {
    
    public static void main(String[] args) throws IOException {
       
        // 0. 입출력 선언 / 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        
        int N = Integer.parseInt(br.readLine());
        // char로 쪼개서 arr에 담음.
        char[] arr = br.readLine().toCharArray();

        // 해당 위치 까지 오는데 사용되는 에너지의 최솟값
        int[] DP  = new int[N]; // (0 ~ N-1)
        // N의 범위가 1~1000 이므로, 최댓값으로 세팅
        Arrays.fill(DP, 999 * 999 + 1); // N = 1000, B, ... ,O 인 경우 => 999 * 999
        DP[0] = 0;
        
        /*
        현재 위치에서 점프 할 수 있는 경우의 수 중 최솟값의 에너지를 같는 경우 탐색
        */
        for(int i=0; i<N-1; i++){
            // B - > O
            if (arr[i] == 'B'){
                for (int j = i+1; j<N; j++){
                    if (arr[j] == 'O'){
                        DP[j] = Math.min(DP[j], DP[i] + (j - i)*(j - i));
                    }
                }
            }
            // O - > J
            else if (arr[i] == 'O'){
                for (int j = i+1; j<N; j++){
                    if (arr[j] == 'J'){
                        DP[j] = Math.min(DP[j], DP[i] + (j - i)*(j - i));
                    }
                }
            }
            // J - > B
            else {
                for (int j = i+1; j<N; j++){
                    if (arr[j] == 'B'){
                        DP[j] = Math.min(DP[j], DP[i] + (j - i)*(j - i));
                    }
                }
            }
        }
        
        // 에너지 값이 갱신되지 않은 경우 == 경로가 없음 
        if (DP[N-1] == 999 * 999 + 1){
            bw.write(-1 + "\n");
        } else bw.write(DP[N-1] + "\n");
        bw.flush();
        
        bw.close();
        br.close();
    }
}

---

[Rewind]

 

1. 어려웠던 점

- 점화식을 도출하는 것이 어려웠다.

- 사용된 에너지의 최솟값을 저장하는 배열인 DP에 초기값으로 최댓값을 저장하는 것이 어려웠다.

(N = 1000 이고, 스타트의 위치에서 1000번째 위치한 'O'로 이동하는 것이 에너지의 최댓값 = 999 * 999,

인것 까지는 쉽게 생각하였지만, 실제로 이와 같은 경우가 입력된 경우, 초기화 해놓은 최댓값 인 999 * 999가 그대로 정답이 된다.

따라서, 어떠한 경우에도 달성 할 수 없는 값으로 초기화를 해놓았어야 했다. (최댓값 + 1)

따라서, DP 배열을 초기화 하는 값은 최댓값 + 1인, (999 * 999 + 1) 이다. )

 

2. 알게된 점

- 배열의 모든 값을 해당 값으로 채우는 "Arrays.fill(배열 이름, 초기화 값)" 함수에 대해 알게 되었다.

- 문자열 형태로 입력되는 것을 문자(char)형으로 쪼개어 주는 ".toCharArray()" 함수에 대해 알게 되었다.

- 새로운 유형의 점화식 도출과정에 대한 사고력이 늘게 되었다.

 

3. 개선 방향

- 더 많은 유형의 DP 문제에 노출되어야 한다.

- 알게된 유용한 함수들을 즉각 다른 문제에 적극적으로 적용해야 한다.