[백준 알고리즘]2449번: 전구_Java

[문제]

최대 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개 전구의 색이 전구번호의 순서대로 하나의 정수로 하나의 빈칸을 사이에 두고 주어진다.

 

[출력]

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

 

[예제]

---

>문제 풀이

 전구의 색을 바꿔서 모든 전구가 같은 색이 되게끔 만들건데, 같은 색의 전구가 붙어있는 경우 하나의 전구 색을 바꾸면 연속되는 같은 색의 전구 역시 색이 바뀝니다.

​

"앞에서부터 색을 바꿔간다." 혹은 "뒤에서 부터 색을 바꿔간다." 이런 패턴이 아니라 중간의 어디의 값에서 부터 바꿔나간 횟수가 최소일 수 있습니다.

​

그래서 이 문제를 풀기 위해 기저 부분까지 들어가서 dp[i][j]의 값을 채워나가는 분할정복 방법을 사용하였습니다.

​

Q. 완전탐색 가능??

A. N이 200까지 K는 20까지 들어오기 때문에 시간초과가 납니다.

>> 완전탐색의 시간 복잡도는 O(N!)인데, 분할정복을 사용하면 O(N^3)으로 해결할 수 있습니다.

​

Q. 왜 O(N!) 인가요?

A. 최악의 경우: 입력으로 들어온 N개의 색이 모두 다르다고 생각해보면, N개중에 하나가 전구 색이 바뀌고, 이제 남은 N-1개의 전구 중 하나를 색을 바꿀 것이고 , 남은 N-2의 전구 중 하나의 색을 바꾸고 ~~

결국 N * (N-1) * ... * 2 * 1= N! 을 해야합니다.

​

​

​

저도 처음에 공부할 때 분할정복으로 전구 색이 바뀌는게 한번에 이해가 안되어서, 그림으로 표현해보았습니다. 아래 코드의 3번이 어떻게 동작하는지 그림과 함께 보면 이해가 쉬울수도..!

	public static int func(int left, int right) {
		//1. 기저점=전구 자기자신
		if(left==right) return 0;
		
        //2. 이미 구한 dp값 존재
		if(dp[left][right]!=0) {
			return dp[left][right];
		}
		
        //3. dp[][] 값을 찾아서 넣어준다.
		int tmp=0;
		dp[left][right]=Integer.MAX_VALUE;
		for(int i=left; i<right; ++i) {
            //3-1. 양쪽 구간의 색이 같은 경우: 0 vs 다른 경우: 1
			tmp= bulb[left]!=bulb[i+1]? 1 : 0;
			dp[left][right]= Math.min(dp[left][right], func(left, i)+func(i+1, right)+tmp);
		}
		return dp[left][right];
	}

 

 

>전체 코드

 

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

public class Main {
	static int N, K;
	static int bulb[], dp[][];
	
	public static void main(String [] args) throws IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st= new StringTokenizer(br.readLine());
		
        //1. 입력받기
		N= Integer.parseInt(st.nextToken());
		K= Integer.parseInt(st.nextToken());
		bulb=new int[N];
		dp= new int[N][N];
		
		st= new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			bulb[i]= Integer.parseInt(st.nextToken());
		}
		
		System.out.println(func(0, N-1));
	}
	
	public static int func(int left, int right) {
		//1. 기저점=전구 자기자신
		if(left==right) return 0;
		
        //2. 이미 구한 dp값 존재
		if(dp[left][right]!=0) {
			return dp[left][right];
		}
		
        //3. 기저부터 dp[][] 값을 찾아서 넣어준다.
		int tmp=0;
		dp[left][right]=Integer.MAX_VALUE;
		for(int i=left; i<right; ++i) {
            //3-1. 양쪽 구간의 색이 같은 경우: 0 vs 다른 경우: 1
			tmp= bulb[left]!=bulb[i+1]? 1 : 0;
			dp[left][right]= Math.min(dp[left][right], func(left, i)+func(i+1, right)+tmp);
		}
		return dp[left][right];
	}
}

https://www.acmicpc.net/problem/2449

2449번: 전구