[C++] 백준 - 전구

문제 

2. 입출력

3. 문제 해설

문제를 읽어보면 최대 K가지의 서로 다른 색을 표현할 수 있는 전구들이 존재하고 이 전구 N개를 한 줄로 배치한다. 

한 줄로 배치한다는 것은 고리 형태가 아닌 자신의 양 옆의 전구만이 자신에게 영향을 줄 수 있다는 뜻이다. 

 

또한 임의의 전구를 하나 잡아 색을 바꾼다. 그런데 이 임의의 전구와 인접한 전구가 같은 색이라면 이 전구 또한 색상이 변한다. 그러면 이 문제는 최소 문제로 쪼갤 수 있다. 

 

바로 옆의 전구가 변했을 때 색이 같다면 변하고 색이 다르다면 변하지 않는 것이다. 그러면 이 문제는 dp를 적용해 memoization 해 가면서 풀 수 있을 거 같다고 생각했다. 

 

이 문제에서 제일 까다로운 점은 임의의 전구부터 시작할 수 있다는 점이다. 

또한 dp를 이용하려면 다음 세 가지 과정을 거쳐야 한다. 

 

1. 첫 번째로 dp배열의 차원과 dp배열이 의미하는 바를 정해야한다. 
2. 문제를 최소 문제로 쪼갠 후 점화식을 찾아야한다.
3. 초기값을 잘 설정해주어야한다.

1번 과정을 수행하기 위해 나는dp[start][end] 를  start부터 end까지 전구를 바꿀 때 같은 색상으로 만들 수 있는 최소 횟수로 정의했다. 

---

 

2번 과정을 생각하기가 힘든데 바로 옆의 전구와 색상이 같을 때는 +1 바로 옆의 전구와 색상이 같을 때는 아무 것도 더해주지 않는다는 것을 생각하면 편하다. 

 

• dp [1][2]의 경우 둘이 같다면 0 둘이 다르다면 1이다. 
• dp [1][3]의 경우 경우의 수는 다음과 같다. 
  • 1번 2번 전구는 색이 같고 2번 3번 전구는 색이 다른 경우
  • 1번 2번 전구 색이 다르고 2번 3번 전구 색이 다른 경우
  • 1번 2번 3번 전구 색이 같은 경우
  • 1번 2번 전구 색이 다르고 2번 3번 전구 색이 같은 경우 

여기서 눈 여겨 볼 것은 첫 번째 경우와 4번째 경우이다. 1번째 경우의 경우 [1][2]의 값에 1번과 3번 값을 비교하여 더해주면 

빨 빨 노

의 경우 1이 되어 차례대로 계산해가는 것이 맞다고 생각할수도 있지만

4번째의 경우 

빨 노 노

의 경우 순서대로 계산하면 dp[1][2]의 값에 1번과 3번이 다르면 2번을 변경해야한다고 잘못 계산된다. 답은 1번만 바꾸면 되는데 말이다!

 

따라서 점화식을 다시 생각해보면 다음과 같다. 

빨 노 노

위의 경우 dp[1][2]와 dp[2][3]을 비교해 더 작은 값과 더 작은 값 인덱스에 포함되지 않은 인덱스와 포함된 인덱스를 비교해줘야한다. 그러면 dp[2][3]은 같은 색이므로 0이고 dp[1][2]는 다른 색이므로 1이 되어서 dp[2][3] + 1 = 1이 정답이 된다. 

dp[1][3] = min(dp[1][1] + dp[2][3] +(전구[1] !=전구[3]), dp[1][2] + dp[3][3] + (전구[2]와 전구[3]))

 

• dp[1][4]의 경우를 생각해보자

위에서 구한 방식대로 잘 구해지는 지 확인해보자

• 1번 2번 3번 4번 전구가 모두 다른 경우

빨 노 초 파

모두 다른 경우 (b는 전구이다.)

dp]1][4]=min(dp[1][1]+dp[2][4]+(b[1]!=b[4]),dp[1][2]+dp[3][4]+(b[2] !=b[4]),dp[1][3]+dp[4][4]+(b[3]!=b[4])) 

dp[1][4]=min(0+2+1 , 1+1+1, 2+0+1) = 3

 

• 중간 2개만 같은 경우

빨 노 노 초

dp]1][4]=min(dp[1][1]+dp[2][4]+(b[1]!=b[4]),dp[1][2]+dp[3][4]+(b[2] !=b[4]),dp[1][3]+dp[4][4]+(b[3]!=b[4])) 

dp[1][4] = min(0+1+1, 1+1+1, 1+0+1) = 2 

정상적으로 잘 나온다. 

 

• 끝 3개가 같은 경우

빨 노 노 노

dp]1][4]=min(dp[1][1]+dp[2][4]+(b[1]!=b[4]),dp[1][2]+dp[3][4]+(b[2] !=b[4]),dp[1][3]+dp[4][4]+(b[3]!=b[4])) 

dp[1][4]  = min(0 + 0 + 1, 1+ 0 + 1, 1+0+1) = 1

정상적으로 잘 나온다. 

---

3번 과정을 수행해보겠다. 

그럼 위의 점화식을 이용해서 초기 값을 설정해줄 때 어떻게 설정해줘야할까

우선 dp[1][1], dp[2][2], dp[3][3]과 같이 자기 자신은 0으로 설정해줘야한다. 또한 dp[1][2], dp[2][3], dp[3][4]등 1씩 차이나는 값들은 만약 두 인접한 전구 색이 같다면 0  다르다면 1로 초기 값을 설정해주어야한다. 

 

그 외의 값은 위의 점화식으로 구할 수 있다. 또한 값은 dp[1][N]의 위치에 저장되게 될 것이다. 

 

따라서 코드는 다음과 같다. 

---

4. 코드

/*
	DP의 가장 중요한 점
	1. dp 배열이 의미하는 것 
	2. 점화식

	이 문제에서 dp[start][end]는 start에서 end까지 하나의 전구 색으로 만들 때 가장 적은 횟수
	
	분할 정복을 이용해야한다.
	dp(1,n)을 구간 1에서 n까지의 전구의 색을 바꾸는 횟수의 최솟값이라고 하고
	dp(1,k) + dp(k+1, n)으로 분할하여 최솟값을 찾는다.

	여기서의 핵심 아이디어는 
	dp[1][4] = min(dp[1][1] + dp[2][4] + (전구[1]!=전구[2]), dp[1][2] + dp[3][4] + (전구[2] != 전구[3]) , dp[1][3] + dp[4][4] + (전구[3] != 전구[4])) 이다. 
*/

#pragma warning (disable : 4996)

#include <cstdio>
#include <algorithm>
#define BULBMAX 202
#define INF 0x3f3f3f3f
using namespace std;
int N, K;

int dp[BULBMAX][BULBMAX];
int bulb[BULBMAX];

int sol(int start, int end) {
	if (start == end) return 0; // 두 개가 같은 경우 0으로 초기화
	
	if (dp[start][end]) return dp[start][end];
	// 바로 옆인 경우
	if (start-1 == end)return (bulb[start] != bulb[end]); // 바로 옆의 경우 같으면 0 다르면 1

	int tmp = INF; //최솟 값을 구하므로 무한대로 초기화해준다.
	for (int i = start; i < end; i++) {
		// 비교하는 대상이 하나는 고정되어 있어야한다. 
		tmp = min(tmp, sol(start, i) + sol(i+1, end) + (bulb[i] != bulb[end]));
	}
	return dp[start][end] = tmp;
}
int main() {
	scanf("%d %d", &N, &K);

	for (int i = 1; i <= N; i++) {
		scanf("%d", &bulb[i]);
	} // 전구 입력 

	printf("%d\n", sol(1, N));

	/*printf("\n");
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			printf("%d ", dp[i][j]);
		}
		printf("\n");
	}*/
	return 0;
}