BOJ 16157 - 블로그

BOJ 16157 - 블로그

부산대 콘테스트 문제에서 $2$개의 색으로 칠하는 그리디 문제가 있었어서 $3$개도 그리디로 가능할 줄 알았는데, DP 문제였다.

$dp[l][r][c]=[l,r]$ 구간에서 $c$색이 칠해져있을 때 모두 올바르게 칠하는데 최소값

이라고 하자.

$l$과 $r$이 $c$와 동일하지 않을 때 까지 구간을 줄여준다.

이제 색을 칠할 수 있는 경우는 세 가지 중 하나로 생각할 수 있다.

1. 남은 구간을 모두 하나의 색으로 칠하기
2. 왼쪽에서부터 어떤 색으로 칠하고 나머지 부분은 현재 색으로 냅두기
3. 오른쪽에서부터 어떤 색으로 칠하기 나머지 부분은 현재 색으로 냅두기

물론 세 가지가 아닌 더 적게도 분리할 수 있지만 굳이 나누자면 이렇다.

이걸 모두 탐색해주는 것은 $O(n)$이므로 $O(3 \cdot n^3)$ 로 문제가 해결된다.

int n;  
string s;  
int dp[101][101][3];  
int idx(char c) {  
   if (c == 'R') return 0;  
   if (c == 'G') return 1;  
   return 2;  
}  
// [l, r]이 c로 칠해져있을 때 최소값  
int fn(int l, int r, int c) {  
   if (l == r) {  
      if (idx(s[l]) == c) return 0;  
      return 1;  
   }  
   int &ret = dp[l][r][c];  
   if (~ret) return ret;  
   ret = 1e9;  
  
   while (l <= r && idx(s[l]) == c)l++;  
   while (r >= l && idx(s[r]) == c)r--;  
   if (l > r) return ret = 0;  
   if (l == r) return ret = 1;  
  
   for (int m = l; m < r; m++) {  
      ret = min(ret, 1 + fn(l, m, 0) + fn(m + 1, r, c));  
      ret = min(ret, 1 + fn(l, m, 1) + fn(m + 1, r, c));  
      ret = min(ret, 1 + fn(l, m, 2) + fn(m + 1, r, c));  
   }  
   for (int m = r; m >= l + 1; m--) {  
      ret = min(ret, 1 + fn(l, m - 1, c) + fn(m, r, 0));  
      ret = min(ret, 1 + fn(l, m - 1, c) + fn(m, r, 1));  
      ret = min(ret, 1 + fn(l, m - 1, c) + fn(m, r, 2));  
   }  
   ret = min(ret, 1 + fn(l, r, 0));  
   ret = min(ret, 1 + fn(l, r, 1));  
   ret = min(ret, 1 + fn(l, r, 2));  
  
   return ret;  
}  
  
void solve() {  
   memset(dp, -1, sizeof dp);  
   cin >> n >> s;  
   debug(n, s);  
   if (n == 1) {  
      cout << 1;  
      return;  
   }  
   cout << min({fn(0, n - 1, 1), fn(0, n - 1, 0), fn(0, n - 1, 2)}) + 1;  
}