[Codeforces 1096D] Easy Problem

[Codeforces 1096D] Easy Problem

문제 설명 : 

알파벳 소문자로 이루어진 문자열이 주어진다. 이 문자열에서 최소 0개이상의 문자들을 삭제해야 하는데 그 조건은 그 문자열에서 순서대로 "h,a,r,d"가 나타나지 않도록 하는 것이다(떨어져 있을 수도 있다). 각 문자에는 가중치(ambiguity)가 존재하여 가중치의 합이 최소가 되도록 제거해야 한다.

풀이 : 

처음에는 그리디로 풀려고 했는데 안되고, dp로 풀어야 하는 문제이다.

전체 문자열(str)을 살피면서 "h,a,r,d"로 하나씩 매칭해본다.

만약 현재 문자 str[i]와 패턴 ptn[j]가 일치한다면 내가 할 수 있는 선택은 두 가지이다. 

1. 현재 ptn(패턴)을 삭제하기로 결정한다. 이 경우의 현재 위치의 ambiguity(=arr[i])를 이전상태&이전 글자인 dp[i-1][j-1]에 더해주어야 한다.

2. 현재 패턴을 삭제하지 않는다. 기존의 값(=dp[i-1][j]) 을 그대로 갖고 오면 된다.

만약 str[i]와 ptn[j]가 일치하지 않는다면 이전 상태의 값(=dp[i-1][j])를 갖고 올 수 밖에 없다.

이렇게 해서 최종 정답은 dp[n][4]에 저장되어 있다.

주의할 점 : 

-

배운 점 : 

처음에는 dp가 아닌 그리디로 접근하려고 했다. 가장 먼저 등장하는 h와 가장 나중에 등장하는 d사이에서 a와 r의 위치 관계를 따지면 될 줄 알았더니 "hardhrd"라는 반례가 존재해서 실패했다. 이 문제가 dp로 풀 수 있는 이유는 '선택의 경우의 수'가 존재하기 때문이다. 이런 문제를 풀 때는 어떤 경우로 선택이 나뉘는지 찾고, 그때 parameter는 어떻게 변하는지 계산하는게 중요하다.

코드 :

이 문제는 전형적인 '선택형 최적 dp' 유형이다. 따라서 dfs로 코드를 짤 수도 있고, for문으로 짤 수도 있다.

반복문으로 짠 코드

#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<stdlib.h>
#include<stack>
using namespace std;
/****************************Contest Template******************************/
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,int> Cord;
typedef long long ll;
typedef unsigned long long ull;
// #define IMP
// #define INF
// const int MOD=
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;
/****************************Contest Template******************************/
const int SIZE= 100009;
const ll INF=1LL<<62;
char str[SIZE];
int arr[SIZE];
ll dp[SIZE][5];
 
int main(){
    int n;    scanf("%d",&n);
    scanf("%s",str+1);
    for(int i=1 ; i<=n ; i++)
        scanf("%d",&arr[i]);
 
    char ptn[]="0hard";
 
    for(int i=0 ; i<=n ; i++)
        dp[i][0]=INF;
 
    for(int i=1 ; i<=n ; i++){
        for(int j=1 ; j<=4 ; j++){
            if(ptn[j]==str[i])
                dp[i][j]=min(dp[i-1][j-1],dp[i-1][j]+arr[i]);
            else dp[i][j]=dp[i-1][j];
        }
    }
    
    printf("%lld\n",dp[n][4]);
    return 0;
}

dfs로 짠 코드

#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<stdlib.h>
#include<stack>
using namespace std;
/****************************Contest Template******************************/
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,int> Cord;
typedef long long ll;
typedef unsigned long long ull;
// #define IMP
// #define INF
// const int MOD=
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;
/****************************Contest Template******************************/
const int SIZE= 100009;
const ll INF=1LL<<62;
 
char str[SIZE];
int arr[SIZE];
ll dp[SIZE][5]={0};
char ptn[]="0hard";
 
ll dfs(int cur,int idx){
    if(idx==0) return INF;
    if(cur==0) return 0;
    if(dp[cur][idx]!=0) return dp[cur][idx];
 
    ll &ret=dp[cur][idx];
 
    if(str[cur]==ptn[idx]) 
        ret=min(dfs(cur-1,idx-1),dfs(cur-1,idx)+arr[cur]);
    else ret=dfs(cur-1,idx);
 
    return ret;
}
 
int main(){
    int n;    scanf("%d",&n);
    scanf("%s",str+1);
    for(int i=1 ; i<=n ; i++)
        scanf("%d",&arr[i]);
    
    printf("%lld\n",dfs(n,4));
    return 0;
}