[백준 2449] 전구 - JAVA

문제 링크 : https://www.acmicpc.net/problem/2449

접근 방법

우선 이 문제를 더 작은 조각의 문제로 나눌 수 있을까? 라는 생각을 가지는게 중요합니다.

당연히 가능합니다.
전구가 한 개만 존재할 때는 무조건 0이고
전구가 두 개만 존재할 때는 두 전구가 같은지 다른지 여부에 따라 0 또는 1이 됩니다.

이런 식으로 부분 문제를 해결하고 그 결과값으로 더 큰 문제들을 해결하면서 마지막에는 총 $N$개의 전구를 같은 색으로 만드는데 최소 횟수를 구할 수 있게 됩니다.

다음으로 $dp[a][b]$에 대한 정의를 해야되는데
저는 $a$부터 $b$까지의 전구를 $a$라는 색으로 밝히는데 최소 횟수라고 정의했습니다.

그리고 $dp$의 탐색은 구간 $DP$(interval DP)로 다음과 같은 순서로 순회하도록 구현했습니다.

분홍색 구간은 자기 자신 위치의 전구를 의미하며 항상 0이고
나머지 부분들은 자신 이전에 해결된 조각들을 활용해서 문제를 해결합니다.

초록색 부분의 문제는 어떻게 해결하는지 설명하자면(dp[a][b]라고 가정했을 때)

• $a$와 $b$ 사이에 존재하는 숫자를 $k$라고 할 때 이 $k$를 $a$부터 $b$까지 이동해갑니다.
• 우리는 $a$부터 $b$까지의 전구 사이에 존재하는 모든 색깔들로 바꿔보면서 어떻게 해야 최소 횟수가 되는지 확인해야 합니다.
• 그러기 위해서는 $a$와 $b$사이 $k$번째 전구 색깔로도 바꿔 봐야하므로 그 값이 기록되어 있는 $[a, k]$ $[k+1, b]$로 최솟값을 계산할 수 있습니다.
• $[a, k]$ $[k+1, b]$까지의 부분 문제에 대해 이미 구해져 있으므로 계산은 다음과 같습니다.
  • $dp[a][k] + dp[k+1][b]$
• 여기서 고려해야할 것은 $k$번째 전구와 $k+1$번째 전구가 같은 색깔인지의 여부인데 다른 경우에는 값을 1 증가시킵니다.
• 위 로직을 $k$를 $a$부터 $b-1$까지 이동시켜가면서 나온 결과값 중 최소가 되는 값을 $dp[a][b]$에 저장합니다.

이렇게 부분 문제들을 수행하다보면 최종적으로 원하는 결과를 $dp[0][N-1]$에서 구할 수 있습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static StringTokenizer st;
    static final int MAX = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] lights = new int[N];
        int[][] dp = new int[N][N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            lights[i] = Integer.parseInt(st.nextToken());
            Arrays.fill(dp[i], MAX);
        }

        int tmp;
        for (int end = 0; end < N; end++) {
            dp[end][end] = 0;
            for (int start = end - 1; start >= 0; start--) {
                for (int mid = start; mid < end; mid++) {
                    tmp = dp[start][mid] + dp[mid+1][end];
                    if (lights[start] != lights[mid+1]) tmp += 1;
                    dp[start][end] = Math.min(dp[start][end], tmp);
                }
            }
        }
        System.out.println(dp[0][N-1]);
    }
}

최적화 방안

이 $dp$문제는 어떻게 최적화 할 수 있을까요?
전구들이 나열되어 있을 때 초기 색깔이 옆의 전구와 같은 경우를 생각해보면 될 것 같습니다.

옆의 전구와 같다면 그 두 전구를 하나로 봐도 되지 않을까요?
그런 생각에서 접근을 했고 $dp$를 조금 더 최적화 할 수 있었습니다!