[BOJ] 백준 2449번 전구 (Java)

#2449 전구

난이도 : 플레 4

유형 : DP

2449번: 전구

▸ 문제

최대 K가지의 서로 다른 색을 표현할 수 있는 전구들이 있다. 이 전구 N개를 다음의 그림과 같이 한 줄로 배치하여 서로 연결한다. (동그라미 안의 숫자는 전구의 색을 의미한다)

 

각 전구는 스위치가 있어서 전구의 색을 임의의 색으로 바꿀 수 있다. 하나의 전구 색을 바꾸는 경우에는, 색이 바뀌는 전구에 인접한 전구가 같은 색이면, 이 전구의 색도 같이 바뀌게 되며 인접한 전구가 다른 색이 나올 때까지 계속 바뀌게 된다. 예를 들어, 위의 그림에서 4번 전구의 색을 2번 색으로 바꾸면, 5번 전구가 4번 전구와 같은 색이었으므로 2번 색으로 바뀌고, 6번 전구도 5번 전구와 같은 색이었으므로 2번 색으로 바뀌게 된다. 즉, 4번 전구의 색을 2번 색으로 바꾸면, 연결된 같은 색의 모든 전구인 4, 5, 6번의 전구가 2번 색으로 바뀌게 되어 아래의 그림과 같이 된다.

 

전구의 수 N과 N개의 전등에 대한 초기 색이 주어질 때, 모든 전구의 색이 하나로 같아질 때까지 최소 몇 번 전구의 색을 바꾸어야 하는지를 구하는 프로그램을 작성하시오. 단, 전구의 각 색은 1부터 K까지의 정수로 나타낸다.

▸ 입력

입력의 첫 번째 줄에는 전구의 수를 나타내는 양의 정수 N과 전구가 표현할 수 있는 색의 수 K가 주어진다. 단, N은 1이상 200이하의 정수이며, K는 1이상 20이하의 정수이다. 두 번째 줄에는 N개 전구의 색이 전구번호의 순서대로 하나의 정수로 하나의 빈칸을 사이에 두고 주어진다.

▸ 출력

첫째 줄에 모든 전구의 색이 하나로 같아질 때까지 전구의 색을 바꾸는 횟수의 최솟값을 하나의 정수로 출력한다.

 

문제 풀이  

문제의 본질을 파악하는 능력이 얼마나 중요한지 알려주는 문제인 것 같다. 본질만 꿰뚫으면 난이도가 급격하게 내려간다. 미숙한 실력을 가진 나로서는 문제의 함정(?)에 앵커링이 되어 이상한 부분에서 한참 헤맸다. 결국 질문에서 색을 고려하지 않아도 된다는 힌트를 얻고나서 문제를 완전히 잘못 접근하고 있다는 것을 깨달았다.

 

이 문제는 간단하게 색이 전혀 상관없는 문제로, 매 싸이클마다 최적인 해를 찾아서 색을 변경해 줄 필요가 없다. 

 

구상

문제의 예시에서는 가운데의 3번 전구의 색을 바꿔줌으로써 마치 빠르게 전구의 색을 바꾸는 것을 보고 어떤 색으로 변경하는 것이 최종적으로 최솟값을 지니는 줄 알았지만 어떤 색이든 상관없다. 실제로 색을 고려해서 풀이를 하면 시간초과가 발생할 가능성이 높다. 

 

다음과 같이 어떤 색으로 바뀌든색을 바꾸는 최소 횟수는 일치하기 때문에 2 → 3으로 바뀌든 2  → 1로 바뀌든 상관이 없다. 그래서 [s,e]구간에서 변경되는 경우를 하나의 사건으로 치부하고 문제를 설계해야 한다.

 

어떤 색이든 최솟값은 동일

 

그러면 이젠 최적해를 찾을 필요없이 주어진 데이터를 분할해가며 모든 케이스를 조사해보면 된다. 그런데 무작정 모든 케이스를 분할정복하면 시간초과가 발생할 수도 있으니 이때 DP를 사용해준다.

• dp[start][end] = [start, end]지점에서 색을 바꾸는 횟수의 최솟값

예를들어, dp[0][7] =2이다.

 

 

설계

1. 구간 [0,n)을 분할정복하여 최소로 변경되는 횟수를 찾아낸다. 
   1. [s,e)구간에서 arr[s]와 일치하지 않는 구간을 분할 지점(i)으로 설정하고 분할한다.  [s,i), [i+1, e)
      1. 일치하지 않는 구간에서 cnt+1을 해준다. 왜냐하면 색이 한 쪽으로 바뀌어야 하기 때문이다. (무슨 색으로 바뀌는지 고려 x)
      2. dp[s][e]에는 가장 적게 변하는 횟수를 저장한다. dp[s][e] = Math.min(dp[s][e],solve(s,i) + solve(i+1, e)+cnt);
2. 이렇게 모든 탐색이 끝나면 dp[0][n-1]을 출력해준다. 

 

풀이 코드 

 색의 종류를 알려주는 변수 k는 함정으로 사용할 필요가 없다.

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

public class Main {
	
	static int INF = 987654321;
	static int[] arr;
	static int[][] dp;
	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());
		
		arr = new int[n];
		dp = new int[n][n];
		for(int i=0; i<n; i++) {
			Arrays.fill(dp[i], INF);
		}
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		System.out.println(solve(0,n-1));
	}
	
	static int solve(int s, int e) {
		if(dp[s][e] != INF) return dp[s][e];
		if(s==e) return 0;
		for(int i=s; i<e; i++) {
			int cnt =0;	
			if(arr[s] != arr[i+1]) {
				cnt=1;
			}
			dp[s][e] = Math.min(dp[s][e],solve(s,i) + solve(i+1, e)+cnt);
		}
		
		return dp[s][e];
	}
}