프로그래밍

https://www.acmicpc.net/problem/5502

[난이도] Gold3
[유형] DP

[풀이]
DP[l][r] : index l부터 index r까지의 문자열을 팰린드롬으로 만들기 위해 삽입해야할 문자의 최수 갯수

점화식 : DP[l][r] = min(
DP[l+1][r]+1, s[l]과 같은 문자를 r+1에 삽입할 때
DP[l][r-1]+1, s[r]과 같은 문자를 l-1에 삽입할 때
DP[l+1][r-1]+1 (if s[l]==s[r]인 경우)
)

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/5502.cpp

#include <string>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int N,dp[5001][5001],inf=9e8;
string s;
int sol(int l,int r){
    if(l>=r) return 0;
    int& ret = dp[l][r];
    if(ret!=-1) return ret;
    ret = inf;
    if(s[l]==s[r]) ret = min(ret,sol(l+1,r-1));
    ret = min(ret,1+sol(l+1,r));
    ret = min(ret,1+sol(l,r-1));
    return ret;
}
int main(){
    cin >> N >> s;
    memset(dp,-1,sizeof(dp));
    cout << sol(0,N-1);
}

https://www.acmicpc.net/problem/2655

[난이도] Gold4
[유형] DP

[풀이]
구조체를 선언해서 index,넓이,높이,무게를 저장한 뒤 넓이의 내림차순으로 정렬한다.
그 뒤에 무게를 기준으로 LIS DP를 적용해서 최적의 케이스를 구해주면 된다.

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2655.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct P{
    int idx,width,height,weight;
};
int N,dp[101],par[101];
P a[101];
bool cmp(P& u,P& v){
    if(u.width > v.width) return 1;
    else if(u.width == v.width) return u.weight > v.weight;
    return 0;
}
int sol(int n){
    int& ret = dp[n];
    if(ret !=-1) return ret;
    ret = a[n].height;
    for(int i=n+1;i<=N;i++){
        if(a[n].weight > a[i].weight && ret < a[n].height+sol(i)) {
            ret = a[n].height+sol(i);
            par[n]=i;
        }
    }
    return ret;
}
void prt(int n,int cnt){
    if(n==0) {
        printf("%d\n",cnt);
        return;
    }
    prt(par[n],cnt+1);
    printf("%d\n",a[n].idx);
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) {
        scanf("%d%d%d",&a[i].width,&a[i].height,&a[i].weight);
        a[i].idx=i;
    }
    sort(a+1,a+1+N,cmp);
    memset(dp,-1,sizeof(dp));

    a[0].weight=9e8;
    sol(0);
    prt(par[0],0);
}

https://www.acmicpc.net/problem/1344

[난이도] Gold4
[유형] DP

[풀이]
DP[cur][a][b] : cur구간까지 진행됬을 때 A는 a만큼 이기고, B는 b만큼 이겼을 때의 확률

DP[cur-1][..][..]의 값을 이용해서 모든 DP[cur][a][b]의 값을 구할 수 있다.

점화식 =>
DP[cur][a][b] = A*B*DP[cur-1][a-1][b-1] (A: A가 이길 확률, B: B가 이길 확률)
+ (1-A)*B*DP[cur-1][a][b-1]
+ A*(1-B)*DP[cur-1][a-1][b]
+ (1-B)*(1-A)*sol[cur-1][a][b]

#include <cstdio>
double A,B,dp[19][19][19];
int k[12] = {0,1,4,6,8,9,10,12,14,15,16,18};
double sol(int cur,int a,int b){
    if(cur<a || cur<b || a<0 || b<0) return 0;
    if(cur==0) return 1;
    
    double& ret = dp[cur][a][b];
    if(ret!=-1.0) return ret;
    ret=0.0;
    ret+=A*B*sol(cur-1,a-1,b-1);
    ret+=(1-A)*B*sol(cur-1,a,b-1);
    ret+=A*(1-B)*sol(cur-1,a-1,b);
    ret+=(1-B)*(1-A)*sol(cur-1,a,b);    
    return ret;
}
int main(){
    scanf("%lf%lf",&A,&B);
    A/=100,B/=100;
    for(int i=0;i<=18;i++)
        for(int j=0;j<=18;j++) 
            for(int k=0;k<=18;k++) dp[i][j][k]=-1.0;


    for(int i=0;i<=18;i++)
        for(int j=0;j<=18;j++) sol(18,i,j);
    
    double ans = 1;    
    for(int i=0;i<12;i++)
        for(int j=0;j<12;j++) ans-=dp[18][k[i]][k[j]];
        
    printf("%.7lf",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1344.cpp

https://www.acmicpc.net/problem/14863

[난이도] Gold4
[유형] DP

[풀이]
전형적인 DP 문제

DP(n,k): 현재 k시간을 썼고 n번 길을 지나야 할때 얻을 수 있는 최대 모금액
점화식 => DP(n,k) =max( DP(n+1,k+[n번째 도보 시간])+[n번째 도보 모금액] ,
DP(n+1,k+[n번째 자전거 시간])+[n번째 자전거 모금액] )

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int N,K,pt[100][2],pr[100][2],dp[100][100001];
int sol(int n,int k){
    if(k>K) return -9e8;
    if(n==N) return 0;
    int& ret = dp[n][k];
    if(ret!=-1) return ret;
    ret = max(sol(n+1,k+pt[n][0])+pr[n][0],sol(n+1,k+pt[n][1])+pr[n][1]);
    return ret;
}
int main(){
    scanf("%d%d",&N,&K);
    for(int i=0;i<N;i++) scanf("%d%d%d%d",&pt[i][0],&pr[i][0],&pt[i][1],&pr[i][1]);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0,0));
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/14863.cpp

https://www.acmicpc.net/problem/7570

[난이도] Gold4
[유형] DP

[풀이]
값이 1씩 증가하는 LIS를 구한다. 이 LIS에 포함되지 않은 숫자들은
모두 앞 또는 뒤로 옮겨줘야 정렬을 할 수 있기 때문에 N-(LIS의 길이) 가 정답이다.

#include <algorithm>
#include <cstdio>
using namespace std;
int N,dp[1000001],v,ans;
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        scanf("%d",&v);
        dp[v] = dp[v-1]+1;
        ans = max(ans,dp[v]);
    }
    printf("%d",N-ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/7570.cpp

https://www.acmicpc.net/problem/2157

[난이도] Gold4
[유형] DP

[풀이]

DP[n][m] : 현재 n 도시에 있고 m개의 도시를 지났을 때 얻을 수 있는 최대 점수

점화식
DP[n][m] max(adj[n][i]+sol(i,m+1)) : i는 n < i 이면서 n에서 i로 가는 경로 존재,
아무 도시도 갈 수 있다면 절대 나올 수 없는 값 -inf를 return하여 정답에서 제외.

#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
int N,M,K,adj[301][301],dp[301][301];
int sol(int n,int m){
    if(n==N) return 0;
    if(m==M) return -9e8;
    int& ret = dp[n][m];
    if(ret!=-1) return ret;
    ret = -9e8;
    for(int i=1;i<=N;i++) if(adj[n][i]) ret = max(ret,adj[n][i]+sol(i,m+1)); 
    return ret;
}
int main(){
    scanf("%d%d%d",&N,&M,&K);
    while(K--){
        int u,v,c;
        scanf("%d%d%d",&u,&v,&c);
        if(u<v) adj[u][v] = max(adj[u][v],c);
    }
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(1,1) > 0 ? sol(1,1):0);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2157.cpp

https://www.acmicpc.net/problem/2306

[난이도] Gold4
[유형] DP

[풀이]
DP[l][r] : l~r의 DNA 서열의 부분 서열들 중에서 길이가 최대가 되는 KOI 유전자의 길이.

k를 l~r-1 증가시키면서 구한 max(DP[l][k]+dp[k+1][r]) 에다

만약 s[i],s[j]가 KOI 유전자일 때, 2+DP[i+1][j-1] 까지 비교해주면 DP[l][r]을 구할 수 있다.

#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
int dp[501][501];
char s[501];
int sol(int l,int r){
    if(l>=r) return 0;
    int& ret = dp[l][r];
    if(ret!=-1) return ret;
    ret = 0;
    if((s[l]=='g'&&s[r]=='c')||(s[l]=='a'&&s[r]=='t')) ret = 2+sol(l+1,r-1);
    for(int i=l;i<r;i++) ret = max(ret,sol(l,i)+sol(i+1,r));
    return ret;
}
int main(){
    scanf("%s",s);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0,strlen(s)-1));
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2306.cpp

https://www.acmicpc.net/problem/3980

[난이도] Gold4
[유형] DP,Bitmask,완전탐색

[풀이]
next_permutation으로 푸니까 TLE로 틀려서 Bitmask DP로 풀었다.
선수 11명, 포지션 11개밖에 안되므로 DP[11][1<11] 배열로
11x2^11 O(22528) 안에 해결이 가능하다.

next_permutation이 아닌 재귀를 활용한 완전탐색으로도 0인 경우에 가지치기를 해주면
시간내에 해결이 가능하다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int tc,a[11][11],dp[11][1<<11],inf=-9e8;
int sol(int n,int msk){
    if(n==11) return 0;
    int& ret = dp[n][msk];
    if(ret!=-1) return ret;
    ret = inf;
    for(int i=0;i<11;i++){
        if(((1<<i)&msk)==0 && a[i][n]){
            ret = max(ret,sol(n+1,msk|(1<<i))+a[i][n]);
        }
    }
    return ret;
}
int main(){ 
    scanf("%d",&tc);
    while(tc--){
        for(int i=0;i<11;i++)
            for(int j=0;j<11;j++) scanf("%d",&a[i][j]);       
        memset(dp,-1,sizeof(dp));
        printf("%d\n",sol(0,0));
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/3980.cpp