블로그( BOJ 16157 )

16157. 블로그 : https://www.acmicpc.net/problem/16157

16157번: 블로그

 

문제 파악하기

• 블로그에 올린 문제는 3가지 색깔(R, G, B)로 칠하게 됩니다.
• 연속된 문제들은 한번에 같은 색깔로 색을 칠할 수 있습니다.
• 문제들을 각각 원하는 색깔로 칠하기 위해서는 최소 몇 번의 색칠 작업이 필요할 지 구해야 합니다.
• 그렇다면 그리디 알고리즘을 사용하면 문제를 풀 수 있을까요? 

 

문제 해결하기

• 아쉽게도 그리디 알고리즘으로는 최적값을 찾는데 무리가 있습니다.
  이 문제는 다이나믹 프로그래밍 알고리즘으로 해결해야 합니다.
• 연속된 문제들을 한번에 칠할 수 있다는 점에 초점을 맞춰봅시다. 그럼 우리는 한번에 칠할 수 있는 경우가 보입니다.
  바로 시작점과 같은 색깔을 가지는 문제가 오른쪽에 있다면 한번에 칠할 수 있습니다.
• 우리는 시작점과 같은 색깔이 있는 경우, 해당 문제까지 칠한 다음에 나머지 구간을 채우는데 필요한 최솟값을 구하면 됩니다.
• DP[l][r][color] = min( DP[l+1][K-1][inp[l]] + DP[K+1][r][color] )
  ( 여기서 K는 l과 같은 색깔을 가진 문제를 의미합니다. )
• 이렇게 점화식을 설계하면 문제를 해결할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define NMAX 105
#define INF 0x7FFFFFFF
using namespace std;
 
int N;
int inp[NMAX];
char str[NMAX];
 
int dp[NMAX][NMAX][5];
 
int convert(char c) {
    switch(c) {
        case 'R': return 1;
        case 'G': return 2;
        default: return 3;
    }
}
 
int sv(int l, int r, int color) {
    if(dp[l][r][color] >= 0) return dp[l][r][color];
    else if(l>r) return dp[l][r][color] = 0;
    else {
        int ll, rr;
 
        ll = l;rr = r;
        while(ll<=rr and inp[ll]==color) ll++;
        while(ll<=rr and inp[rr]==color) rr--;
 
        if(ll > rr) return dp[l][r][color] = 0;
        else {
 
            int ret = INF;
            for (int i=ll;i<=rr;i++) {
                if(inp[i] == inp[ll]) {
                    ret = min(ret, sv(ll+1, i-1, inp[ll]) + sv(i+1, rr, color) + 1);
                }
            }
 
            return dp[l][r][color] = ret;
        }
    }
}
 
int main() {
    scanf("%d", &N);
    scanf("%s", str);
    for(int i=0;str[i]!='\0';i++) inp[i+1] = convert(str[i]);
 
    memset(dp, -1, sizeof(dp));
    printf("%d", sv(1, N, 0));
}