백준 2449번 전구

사용한 알고리즘: DP


 문제에 주어진 조건에 따라 N개의 전구들을 하나의 색으로 바꾸는 최소 횟수를 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 6~7)
 'dp[a][b] : a~b 전구를 같은 색으로 바꾸는 최소 횟수' 라고 설정하였습니다.
 모든 묶음 (a~b) 는 무조건 맨 앞 a전구 색으로 맞춰져 있다고 생각하겠습니다.
 사실 잘 생각해보시면 (a~b) 전구 묶음을 맨 앞의 a전구 색으로 맞춰도 오류가 없습니다...

(2) (코드 15~17)
 기저경우인 2개묶음을 먼저 계산해 줍니다. 모든 전구를 바로 옆 전구와 묶어줍니다.
 두 전구의 색이 같은경우 dp[i][i+1] = 0 이고, 두 전구 색이 다른경우 이를 맞춰주는 한번의 횟수 dp[i][i+1] = 1 라고 설정해 줍니다.
 1개의 묶음 dp[i][i] = 0 임은 자명합니다...

(3) (코드 19~35)
 3개 묶음, 4개 묶음, ... , N개 묶음 으로 전구들을 묶어봅니다.
 (k-1개의 묶음) a 전구부터 a+k 전구까지의 횟수  dp[a][a+k] 는 전체 a~a+k를 2개 묶음으로 나누어, 이를 합치는 경우들 중 최소 횟수의 값입니다.
 예를들어 a, a+1, a+2, a+3 전구들을 묶는 dp[a][a+3]의 계산은 다음 경우를 고려해야 합니다.
 1. a / a+1~a+3         -> dp[a][a] + dp[a+1][a+3] ( a와 a+1 색이 다르면 ) +1
 2. a~a+1 / a+2~a+3  -> dp[a][a+1] + dp[a+2][a+3] ( a와 a+2 색이 다르면 ) +1
 3. a~a+2 / a+3         ->  dp[a][a+2] + dp[a+3][a+3] ( a와 a+3 색이 다르면 ) +1
 위의 1,2,3 중 최소 값이 dp[a][a+3] 값이 됩니다.

	#include <bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	const ll INF = 10987654321;
	int N, K, color[222];
	// dp[i][j] : i~j 를 같은색으로 바꿨을 때 최소 경우의 수 ( 맨앞의 색으로 맞춰줬다 생각)
	ll dp[222][222];
	int main(){ios_base::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
	cin >> N >> K;
	for(int i=1; i<=N; ++i) cin >> color[i];
	// 2개씩 바로 옆과 색을 맞추는 경우. ( 기저 )
	for(int i=1; i<N; ++i)
	if(color[i]!=color[i+1]) dp[i][i+1] = 1LL; // 두 전구가 다른색인 경우
	// 3 ~ N 개씩 (t+1개씩) 묶어보기
	for(int t=2; t<=N; ++t){
	for(int i=1; i<=N; ++i){
	if(i+t>N) break;
	// 처음 infimum 설정
	dp[i][i+t] = INF;
	// t+1 개 묶음을 두 묶음으로 쪼개보기
	for(int k=0; k<t; ++k){
	ll temp = dp[i][i+k]+dp[i+k+1][i+t];
	// 두 묶음은 각각 맨 앞의 전구 색으로 맞춰져 있다.
	if(color[i]!=color[i+k+1])
	temp++; // 두 묶음의 맨 앞 색이 다르면 맞춰주는 횟수 +1 추가
	// dp값 최신화
	dp[i][i+t] = min(dp[i][i+t], temp);
	}
	}
	}
	cout << dp[1][N] << '\n';
	return 0;
	}

view raw BOJ 2449.cpp hosted with ❤ by GitHub