[BOJ 백준] 전구 (2449) Java

링크 : https://www.acmicpc.net/problem/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개 전구의 색이 전구번호의 순서대로 하나의 정수로 하나의 빈칸을 사이에 두고 주어진다.

 

출력 : 

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

 

예제 입력 : 

10 3
1 1 2 3 3 3 2 2 1 1

 

예제 출력 : 

2

 

 

접근법 : 

1) 어떻게 풀 것인가?

N이 200으로 작지 않으나, K가 20이어서 완전탐색 기반으로 간다면 시간초과가 예상된다.

 

위 예제를 보고 있으면 전구를 어떤색으로 바꿔야하지만 자꾸 떠올라서, 

정신차리고 DP, 분할정복 형태로 풀기로 했다.

 

아이디어는 이렇다. 아래 그림처럼 전체 전구를 아예 1개까지 분할한다.

그 다음에 input값의 차이가 없는 경우 0, 있는 경우 1을 더해준다.

	static int divideConquer(int start, int end) {
		// 1. 자기 자신이면 return 0;
		if (start == end)
			return 0;

		// 2. 이미 dp[start][end]를 알고 있으면 return
		if (dp[start][end] != 0)
			return dp[start][end];

		// 3. 가장 바닥까지 쪼개서 값 확인
		dp[start][end] = Integer.MAX_VALUE; // 최대치로 두고 갱신 예정
		int left, right;
		for (int i = start; i < end; i++) {
			left = divideConquer(start, i);
			right = divideConquer(i + 1, end);

			// 3-1. 양쪽 구간의 색이 같은 경우
			if (input[start] == input[i + 1]) {
				dp[start][end] = Math.min(dp[start][end], left + right);
			}
			// 3-2. 양쪽 구간의 색이 다르면 비용 1 추가
			else {
                dp[start][end] = Math.min(dp[start][end], left + right + 1);
            }
		}
		return dp[start][end];
	}

전체 코드는 아래 참고.

 

2) 시간복잡도

최악의 경우 N^3 예상되나, N이 200으로 작아 무리 없음

(Java 기준 -  184ms)

 

3) 공간복잡도

N)(200)이 크지 않아 고려하지 않음

 

4) 풀면서 놓쳤던점

특별히 없음.

 

5) 이 문제를 통해 얻어갈 것

분할정복 코드 작성법

 

Java 코드 : 

import java.io.*;
import java.util.*;

// 2449 전구
public class Main {

	static int N, K;
	static int[] input;
	static int[][] dp;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		// 1. 입력받기
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		input = new int[N];
		dp = new int[N][N];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			input[i] = Integer.parseInt(st.nextToken());
		}
		divideConquer(0, N - 1);

		bw.write(String.valueOf(dp[0][N - 1]));

		bw.flush();
		bw.close();
		br.close();
	}

	static int divideConquer(int start, int end) {
		// 1. 자기 자신이면 return 0;
		if (start == end)
			return 0;

		// 2. 이미 dp[start][end]를 알고 있으면 return
		if (dp[start][end] != 0)
			return dp[start][end];

		// 3. 가장 바닥까지 쪼개서 값 확인
		dp[start][end] = Integer.MAX_VALUE; // 최대치로 두고 갱신 예정
		int left, right;
		for (int i = start; i < end; i++) {
			left = divideConquer(start, i);
			right = divideConquer(i + 1, end);

			// 3-1. 양쪽 구간의 색이 같은 경우
			if (input[start] == input[i + 1]) {
				dp[start][end] = Math.min(dp[start][end], left + right);
			}
			// 3-2. 양쪽 구간의 색이 다르면 비용 1 추가
			else {
                dp[start][end] = Math.min(dp[start][end], left + right + 1);
            }
		}
		return dp[start][end];
	}

}