https://www.acmicpc.net/problem/2449
오늘 풀어볼 문제는 전구의 색을 변경하는 문제이다.
전구마다 색이 정해져 있는 상태에서 전구의 색을 변경하면 연결되어 있는 같은 색의 전구들의 색이 똑같이 변경되며
이 과정을 통해 모든 전구를 같은 색으로 만드는 문제이다.
처음에는 전구의 색이 K개이므로 K를 가지고 전구의 색을 바꾸는 횟수를 세려고 했다.
그러나 이렇게 되면 너무 많은 경우가 생겨 시간 안에 처리하지 못하는 경우가 발생한다.
따라서 이 문제는 색의 개수 K에 집중하는 것이 아닌 각 부분을 작은 문제로 보고
다이나믹 프로그래밍 방식으로 해결해야 한다.
시작 부분과 끝 부분을 두고, 그 사이에 인덱스를 위치시켜 시작 부분~인덱스, 인덱스+1~끝 부분으로 나눈다.
이후 인덱스+1 부분과 시작 부분의 전구의 색이 다르면 횟수를 1 증가시킨다.
이렇게 작은 문제들로 나눠 DP 테이블을 채워 나가 마지막에 횟수를 세면
그것이 전체 전구의 색을 같게 만드는 데 필요한 횟수가 된다.
이제 위의 개념을 바탕으로 코드를 작성해 보자.
#include <iostream>
#include <vector>
#define INF 987654321
using namespace std;
// 전구 벡터
vector<int> bulbs(201);
// DP 벡터
vector<vector<int>> dp(201, vector<int>(201, -1));
int min(int a, int b) {
if (a < b)
return a;
else
return b;
}
int calc(int start, int end) {
// 이미 채워진 값이라면 그대로 가져옴
int &ret = dp[start][end];
if (ret != -1)
return ret;
// 시작 위치와 끝 위치가 같음
// 구간이 0인 경우
if (start == end)
return ret = 0;
ret = INF;
// 시작 위치 색과 i+1번째 위치 색이 다를 경우 count 증가
for (int i = start; i <end; i++) {
int count = 0;
if (bulbs[start] != bulbs[i+1])
count++;
ret = min(ret, calc(start, i)+calc(i+1,end)+count);
}
return ret;
}
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> bulbs[i];
}
cout << calc(0, n-1);
return 0;
}
이번 문제는 다이나믹 프로그래밍 개념을 확실히 이용하는 문제였다.
전구의 색 개수에 초점을 두는 것이 아닌 색이 바뀌는 구간을 이용해 작은 문제로 분할하는 아이디어를 도출해내기가 까다로운 문제였던 것 같다.
이 문제를 끝으로 총 6회차 동안의 DP 공부가 끝이 났다.
처음 배울 때 정말 아무것도 모른 상태로 이해도 없이 따라가기만 했구나 라는 생각이 들 정도로 많은 것을 알아가는 것 같다.
다이나믹 프로그래밍이라는 기법은 정말 다양하게 사용할 수 있다는 것을 알게 되었고 앞으로는 더 적극적으로 사용할 수 있을 것 같다.
작은 문제로 분할하고 그 결과를 기억한다는 기본적인 개념을 항상 잊지 말고 꼼꼼히 문제를 뜯어보는 습관을 가져야겠다.
