[백준] 2449번 : 전구 - JAVA

백준 2449 전구

 
 
 
DP 문제 풀이 팁을 유튜브로 찾아보던 중 '개발자로 취직하기' 유튜버님의 DP 문제해설 영상을 보게 되어 해당 문제를 풀게 되었다.
 
해설 영상을 기존에 봤기 때문에 해당 문제에 대해 다시 정리한다.
 
 

풀이 접근

4. 2개 이상 전구들 간의 최솟값 계산

1. 입력 받은 숫자를 전구 배열에 추가
 - 입력 받은 숫자가 연달아 입력되는 경우 색상 변경 시 일괄 변경되므로 추가하지 않음
2. 전구 배열에 추가된 숫자 개수만큼 DP 배열 크기 설정
3. DP 배열 최댓값으로 초기화(나중에 최솟값 비교)
 - |1,1|2,2|3,3|4,4|5,5| 0으로 세팅
 
 

최솟값 계산 기준

 
먼저 인접해 있는 동일한 수를 모두 배제한 전구 배열(lamp)에 5개의 요솟수가 있다고 가정한다.
이후 1개부터 5개로 분할하여 나온 묶음에서 하위 묶음을 찾아 색상을 변경하는데 필요한 횟수를 구한다.
 

1. 분할 - for 1

1개씩 분할 | 1,1 | 2,2 | 3,3 | 4,4 | 5,5  -> 1개씩 분할하는 경우 당연히 색상을 변경할 필요가 없어 0회
2개씩 분할 | 1,2 | 2,3 | 3,4 | 4,5
3개씩 분할 | 1,3 | 2,4 | 3,5
....
 

2. 분할되어 나누어진 묶음 - for 2

그리고 n개로 분할된 각 묶음마다 하위 묶음이 존재한다.
ex) [1,3] = [1,1][2,3], [1,2][3,3]
 

3. 하위 묶음 - for 3

2개씩 분할한 묶음 중 [1,2]를 보면 [1,1] = 0과 [2,2] = 0을 더하여 생성되지만 [1,2]의 값은 1인 것을 확인할 수 있다.
[1,1]과 [2,2]는 lamp배열에서 보면 각각 다른 숫자이기 때문에 서로 같은 숫자인지 확인하여 다르면 1을 추가해야 한다.
 
정리하면 다음과 같은 공식이 만들어진다.

[1,2] = [1,1] + [2,2] + ( lamp[1] == lamp[2] ? 0 : 1 )

 
 
그리고 1, 2, 3번의 과정을 구현하면 아래와 같다.
 

최솟값 찾기 구현 소스

/**
 * 2개 이상의 전구들 간의 최솟값 계산
 */
static void getMinValue() {
    // 전구 분할 개수
    for (int size = 2; size < dp.length; size++) {
        // 분할되어 나누어진 전구 묶음 개수
        for (int start = 1; start <= dp.length - size; start++) {
            int end = start + size - 1;

            // 현재 전구 묶음의 하위 묶음에 대한 최솟값 찾기
            for (int mid = start; mid < end; mid++) {
                /*
                하위 묶음 값 계산
                - 전구 배열의 묶음 사의 값이 다르면 + 1
                 */
                int value = dp[start][mid] + dp[mid + 1][end] + (lamp[start] != lamp[mid + 1] ? 1 : 0);
                
                dp[start][end] = Math.min(value, dp[start][end]);
            }
        }
    }
}

 
 

전체 소스

public class Main {

    static final int MAX_NUM = (1 << 31) -1;
    static int[] lamp;
    static int[][] dp;

    /**
     * 2개 이상의 전구들 간의 최솟값 계산
     */
    static void getMinValue() {
        // 전구 분할 개수
        for (int size = 2; size < dp.length; size++) {
            // 분할되어 나누어진 전구 묶음 개수
            for (int start = 1; start <= dp.length - size; start++) {
                int end = start + size - 1;

                // 현재 전구 묶음의 하위 묶음에 대한 최솟값 찾기
                for (int mid = start; mid < end; mid++) {
                    /*
                    하위 묶음 값 계산
                    - 전구 배열의 묶음 사의 값이 다르면 + 1
                     */
                    int value = dp[start][mid] + dp[mid + 1][end] + (lamp[start] != lamp[mid + 1] ? 1 : 0);

                    dp[start][end] = Math.min(value, dp[start][end]);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        int lampLength = n + 1;

        lamp = new int[lampLength];
        int cntNum = 1;

        /*
        1. 전구 색상 입력
        2. 색상 변경 시 인접한 숫자는 한 번에 변경되므로 동일한 숫자는 추가 X
         */
        for(int i = 1; i < lampLength; i++){
            int num = Integer.parseInt(st.nextToken());

            if (lamp[i - 1] == num) {
                lampLength--;
                i--;
                continue;
            }

            cntNum++;
            lamp[i] = num;
        }

        // 3. 인접하지 않은 숫자를 기준으로 숫자 개수만큼 dp 크기 설정
        dp = new int[cntNum][cntNum];

        /*
        4. DP 배열 최댓값으로 초기화
        4-1. 1,1|2,2|3,3|4,4|5,5 0으로 남김
         */
        for (int i = 1; i < dp.length; i++) {
            for (int ii = 1; ii < dp[i].length; ii++) {
                dp[i][ii] = MAX_NUM;
            }
            dp[i][i] = 0;
        }

        getMinValue();

        System.out.println(dp[1][dp[1].length - 1]);
        br.close();
    }


}

 
 
 
- 참고 레퍼런스

https://www.youtube.com/watch?v=N8MG6OetuNs