[CF 1114D] Flood Fill

[CF 1114D] Flood Fill - 1900

문제 설명 : 

n개의 수가 주어지고 이 중에서 시작할 수 1개를 고른다. 그리고 매 시행마다 시작 위치가 포함된 똑같은 수로 연결된 한 덩어리를 다른 숫자로 바꿀 수 있다. 이때 모든 숫자를 똑같은 숫자로 바꾸는데 필요한 최소 시행 수를 구하여라.

풀이 : 

우선 맨 처음에 n개의 수를 입력받으면 unique연산을 취해서 인접해 있으면서 값이 같은 수를 미리 없애준다. 인접한 같은 수는 어차피 한 덩어리이므로 정답에 영향이 없기 때문이다. unique를 취한 후에는 인접한 숫자끼리는 모두 다를 것이라는 확신을 할 수가 있다. 

그러고 난 뒤에 각 시행에서 내가 신경써야할 것은 시행의 가장 왼쪽 수(l)와 가장 오른쪽 수(r)가 같은지 여부이다. 만약에 같다면 l과 r사이에 있는 시행횟수에서 1을 더해주면 된다. 만약에 다르다면 여기서 나는 왼쪽을 줄일 수도 있고 오른쪽을 줄일 수도 있으므로 2개의 dp재귀함수를 실행해봐서 작은 값을 취하면 된다.

주의할 점 : 

-

배운 점 : 

전형적인 선택형 최적 dp유형인데 그걸 깨닫지 못했다. 어디선가 풀어봤던 문제처럼 생겼는데 아쉽다.

코드 :

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b)
    { a=_a; b=_b; }
    const bool operator<(const S &o) const{
        return a<o.a;}
};
priority_queue<int,vector<int>,greater<int>> mpq;
const int SPACE=0,NL=1;  string exm;
inline void showAll(vector<int> &v,int sep){ //0=space,1="\n"
    for(int &here:v) printf("%d%c",here,(sep)?'\n':' '); }
inline void exf(void){ cout<<exm<<"\n"; exit(0); }
inline vector<int> int_seperation(int N,int d=10){
    vector<int> v; while(N){v.push_back(N%d); N/=d;}
    reverse(v.begin(),v.end()); return v; }
/*********************Contest Template***********************/
const int SIZE= 5009;
 
int arr[SIZE];
int dp[SIZE][SIZE];
int dpf(int l,int r){
    int &ret=dp[l][r];
    if(ret!=-1) return ret;
    if(l>=r) return 0;
 
    if(arr[l]==arr[r])
        ret=dpf(l+1,r-1)+1;
    else{
        ret=min(dpf(l+1,r)+1,dpf(l,r-1)+1);
    }
    return ret;
}
 
int main(){
    int n;  scanf("%d",&n);    
    for(int i=1 ; i<=n ; i++){
        scanf("%d",&arr[i]);
    }
 
    n=unique(arr+1,arr+1+n)-arr-1;
 
    for(int i=1 ; i<=n ; i++){
        for(int j=1 ; j<=n ; j++){
            dp[i][j]=-1;
        }
    }
 
    printf("%d\n",dpf(1,n));
 
    return 0;
}