프로그래밍

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

[난이도] Gold2
[유형] DP

[풀이]
트리 DP로 해결할 수 있는 문제입니다.
3차원 DP로 풀었습니다.
DP[n][p][c] : 현재 n번 마을, 부모 마을의 우수마을여부가 p, n번 마을의 우수마을 여부가 c 일때의 최댓값
              (1인 경우 우수마을, 0인 경우 일반마을)

c==1 인 경우 n의 인접한 자식 마을들은 무조건 우수마을이 될 수 없으므로
   sol(nxt,c,0) (nxt는 n의 자식 마을) 값들을 더해주면 됩니다.

c==0 인 경우 부모 마을의 우수마을여부 p를 따져봐야 합니다.
   i) p==1 (부모가 우수마을인 경우)
     이 경우에는 n의 자식은들은 인접한 마을인 n이 우수마을인 것이 보장되기 때문에
     우수마을이든 일반 마을이든 상관이 없습니다.
     그러므로 max(sol(nxt,0,0),sol(nxt,0,1)) 과 같이 우수마을,일반마을로 선택한 경우중 최댓값을 더해주면 됩니다.

   ii) p==2 (부무가 일반마을인 경우)
     n이 일반마을이고, n의 부모도 일반 마을인 경우 입니다.
     이 경우 n의 자식들 중에 반드시 한 마을은 우수 마을이어야 합니다.
     n의 자식 nxt들 중 한 마을은 무조건 우수 마을로 결정한 모든 경우를 고려서해서
     그 중 최댓값을 더해주면 됩니다.

3차원 dp 풀이

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int N,a[10001],dp[10001][2][2],visit[10001];
vector<int> tmp[10001],adj[10001];
int sol(int n,int p,int c){
    int& ret = dp[n][p][c];
    if(ret!=-1) return ret;
    ret=0;
    if(c==1){
        ret=a[n];
        for(auto nxt : adj[n]) ret+=sol(nxt,1,0);
    }else{
        if(p==1){
            for(auto nxt :adj[n]) ret+=max(sol(nxt,0,0),sol(nxt,0,1));
        }else{
            vector<int> v;
            int t=0;
            for(auto nxt :adj[n]) {
                int j = max(sol(nxt,0,0),sol(nxt,0,1));
                t+=j;
                v.push_back(j);
            }
            int mv=0;
            for(int i=0;i<adj[n].size();i++){
                int tt=t;
                tt-=v[i];
                tt+=sol(adj[n][i],0,1);
                mv=max(tt,mv);
            }
            ret=mv;
        }
    }
    return ret;
}
void tree(int n){
    visit[n]=1;
    for(auto nxt : tmp[n]){
        if(!visit[nxt]) {
            adj[n].push_back(nxt);
            tree(nxt);
        }
    }
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&a[i]);
    for(int i=0;i<N-1;i++) {
        int u,v;
        scanf("%d%d",&u,&v);
        tmp[u].push_back(v);
        tmp[v].push_back(u);
    }
    tree(1);
    memset(dp,-1,sizeof(dp));
    printf("%d",max(sol(1,0,0),sol(1,0,1)));
}

3번 조건에 의해 부모의 우수마을 여부도 알고 있어야 하기 때문에 위와 같이 3차원 DP로 풀었는데
다른 분들의 풀이를 보고 알았는데
3번 조건은 무시해도 되는 조건이라 2차원 dp로도 해결이 가능합니다.
우리가 우려하는 아래와 같이 일반마을이 세번 연속 나오는
트리 모양은 절대로 정답이 될 수 없기 때문입니다.
점화식이 max를 구하는 방식으로 되어 있기 때문에 2번 노드를 우수마을로 선택한 경우가 정답의 후보가 될수밖에 없습니다.
   1(0)
   2(0)
 3(0) 4(0)
 1(1) 1(1)

2차원 dp 풀이

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int N,a[10001],dp[10001][2];
vector<int> adj[10001];
int sol(int n,int k,int p){
    int& ret = dp[n][k];
    if(ret!=-1) return ret;
    ret=0;
    if(k==1) ret=a[n];
    for(auto nxt : adj[n]){
        if(nxt!=p){
            if(k==0) ret+=max(sol(nxt,0,n),sol(nxt,1,n));
            else ret+=sol(nxt,0,n);
        }
    }
    return ret;
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&a[i]);
    for(int i=0;i<N-1;i++) {
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    adj[0].push_back(1);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0,0,0));
}

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

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

[난이도] Gold3
[유형] DP

[풀이]
['abb' 의 부분수열은 {'a'}, {'b'}, {'b'}, {'ab'}, {'ab'}, {'bb'}, {'abb'}]
지문의 위 부분을 잘 봐야 합니다. 'ab'가 두번 나오기 때문에 부분수열은 연속된 수들이 아니어도 됩니다.

연속이 아니어도 아래와 같은 점화식의 DP로 해결이 가능합니다.
DP[l][r] = DP[l+1][r]+DP[l][r-1]-DP[l+1][r-1] (s[l]!=s[r])
           DP[l+1][r]+DP[l][r-1]+1 (s[l]==s[r])

s[l]!=s[r] 일때 DP[l+1][r-1]을 빼주는 이유는 DP[l+1][r],DP[l][r-1] 에 모두 DP[l+1][r-1]가
포함되어 있기 때문에 중복되지 않도록 빼주는 것입니다.

반면 s[l]==s[r] 일 때는 양 끝에 s[l],s[r]을 붙임으로써 DP[l+1][r-1]만큼이 그대로 더해지므로
빼지 않아도 되며, 부분수열 {s[l],s[r]}인 경우를 추가해야 하므로 1을 더해주었습니다.

#include <string>
#include <iostream>
#include <cstring>
using namespace std;
string s;
int dp[31][31];
int sol(int l,int r){
    if(l==r) return 1;
    if(l>r) return 0;
    int& ret=dp[l][r];
    if(ret!=-1) return ret;
    ret = sol(l+1,r)+sol(l,r-1);
    if(s[l]!=s[r]) ret-=sol(l+1,r-1); 
    else ret++;
    return ret; 
}
int main(){
    cin >> s;
    memset(dp,-1,sizeof(dp));
    cout << sol(0,s.size()-1);
}

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

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

[난이도] Gold3
[유형] DP

[풀이]
dp[i] : i번 노드에서 leaf 노드까지 연결된 간선만 끊을 수 있을 때, 필요한 최소 cost

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int T,N,M,D,dp[1001];
vector<pair<int,int>> adj[1001];
int sol(int n,int p){
    int& ret = dp[n];
    if(ret!=-1) return ret;
    ret=0;
    if(p!=0&&adj[n].size()==1) ret=1e8;
    else{
        for(auto [nxt,d] : adj[n]){
            if(nxt!=p) ret+=min(d,sol(nxt,n));
        }
    }
    return ret;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&N,&M);
        for(int i=1;i<=N;i++) adj[i].clear();
        while(M--){
            int u,v,d;
            scanf("%d%d%d",&u,&v,&d);
            adj[u].push_back({v,d});
            adj[v].push_back({u,d});
        }
        memset(dp,-1,sizeof(dp));
        printf("%d\n",sol(1,0));
    }
}

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

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

[난이도] Gold5
[유형] DP

[풀이]
DP[r][c][k] : 파이프의 끝이 r,c에 있고 모양이 k일때 (N,N)에 도착할 수 있는 경우의 수, (0:가로,1:세로,2:대각선)
현재 모양 k에 따라 dp 점화식을 세워주면 됩니다.

#include <cstdio>
#include <cstring>
using namespace std;
using ll = long long;
int N,board[35][35];
ll dp[35][35][3];
ll sol(int r,int c,int k){
    if(r==N&&c==N) return 1;
    ll& ret = dp[r][c][k];
    if(ret!=-1) return ret;
    ret=0;
    if(k==0){
        if(!board[r][c+1]) {
            ret+=sol(r,c+1,0);
            if(!board[r+1][c+1] && !board[r+1][c]) ret+=sol(r+1,c+1,2);
        }
    }
    if(k==1){
        if(!board[r+1][c]) {
            ret+=sol(r+1,c,1);
            if(!board[r+1][c+1] && !board[r][c+1]) ret+=sol(r+1,c+1,2);
        }
    }
    if(k==2){
        if(!board[r][c+1]) ret+=sol(r,c+1,0);
        if(!board[r+1][c]) ret+=sol(r+1,c,1);
        if(!board[r+1][c+1] && !board[r+1][c] && !board[r][c+1]) ret+=sol(r+1,c+1,2);        
    }
    return ret;
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) 
            scanf("%d",&board[i][j]);
    for(int i=1;i<=N+1;i++) board[N+1][i]=board[i][N+1]=1;
    memset(dp,-1,sizeof(dp));
    printf("%lld",sol(1,2,0));
}

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

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

[난이도] Gold4
[유형] DP

[풀이]
DP[n][m] : 첫번째 문자열의 문자를 앞에서부터 n개 사용했고, 두번째 문자열의 문자를 앞에서부터 m개 사용했을 때,
           세번째 문자열의 아직 사용하지 않은 문자열을 채울 수 있으면 1, 없으면 0을 return

#include <string>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int tc,dp[201][201];
string a,b,c;
int sol(int n,int m){
    if(n+m==c.size()) return 1;
    int& ret = dp[n][m];
    if(ret!=-1) return ret;
    if(n<a.size() && c[n+m]==a[n] && sol(n+1,m)) return ret=1;
    if(m<b.size() && c[n+m]==b[m] && sol(n,m+1)) return ret=1;
    return ret=0;
}
int main(){
    scanf("%d",&tc);
    for(int i=1;i<=tc;i++){
        cin >> a >> b >> c;
        memset(dp,-1,sizeof(dp));
        string ret = sol(0,0) ? "yes":"no";
        cout << "Data set " << i << ": " << ret << '\n';
    }
}

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

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

[난이도] Gold4
[유형] DP

[풀이]
어떤 칸 (r,c) 의 한 숫자를 선택할 경우 어차피 r-1,r+1행은 선택할 수가 없습니다.
그러므로 r행의 숫자들을 선택할 때 이왕이면 최대한 많은 사탕을 선택하는 것이 좋습니다.

r행에서 선택할 수 있는 사탕의 최댓값은 dp를 이용해 구할 수 있습니다.
그리고 구한 값을 maxv 배열에 저장해 놓은 뒤

이 배열의 값을 이용해 같은 방식으로 어떤 열이 선택되는지를 dp로 구해주면 됩니다.
dp2[r] : r행을 선택 했을 때, 얻을 수 있는 사탕의 최대 개수.
dp2[r] = maxv[r]+max(dp2[r+2],dp2[r+3]);

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstring>
using namespace std;
int M,N,board[200000],dp1[200000],dp2[200000],maxv[200000];
int sol(int r,int c){
    if(c>=N) return 0;
    int& ret = dp1[r*N+c];
    if(ret!=-1) return ret;
    return ret=board[r*N+c]+max(sol(r,c+2),sol(r,c+3));
}
int sol2(int r){
    if(r>=M) return 0;
    int& ret =dp2[r];
    if(ret!=-1) return ret;
    return ret=maxv[r]+max(sol2(r+2),sol2(r+3));
}
int main(){
    while(1){
        scanf("%d%d",&M,&N);
        if(N==0 && M==0) break;
        memset(dp1,-1,sizeof(dp1));
        memset(dp2,-1,sizeof(dp2));
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                int v;
                scanf("%d",&v);
                board[i*N+j]=v;
            }
            maxv[i] = max(sol(i,0),sol(i,1));
        }
        printf("%d\n",max(sol2(0),sol2(1)));
    }
}

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

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

[난이도] Gold4
[유형] DP

[풀이]
dp[a][b] : 전체 돌의 개수가 T이면서 a<=b<=T-a-b 일 때, 세 개의 돌을 같게 만들 수 있으면 1,
           아니면 0을 저장

위와 같이 점화식을 세운 뒤, a<=b<=T-a-b 조건을 만족하도록 정렬해주면서
Top-Down dp 함수를 짜주면 됩니다.
이전 상태로 돌아가지 않도록 visit 배열을 선언하면 방문 여부를 체크해주었습니다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int arr[3],dp[501][501],T,visit[501][501];
int sol(int a,int b){
    if(a<=0 || b<=0 || T-a-b<=0) return 0;
    if(a==b && a==T-a-b) return 1;
    if(visit[a][b]) return 0;
    visit[a][b]=1;
    int& ret = dp[a][b];
    if(ret!=-1) return ret;

    int tmp[3];
    int A=a,B=b,C=T-A-B;

    tmp[0]=2*A,tmp[1]=B-A,tmp[2]=C;
    sort(tmp,tmp+3);
    if(sol(tmp[0],tmp[1])) return ret=1;

    tmp[0]=A,tmp[1]=2*B,tmp[2]=C-B;
    sort(tmp,tmp+3);
    if(sol(tmp[0],tmp[1])) return ret=1;

    tmp[0]=2*A,tmp[1]=B,tmp[2]=C-A;
    sort(tmp,tmp+3);
    if(sol(tmp[0],tmp[1])) return ret=1;

    return ret=0;
}

int main(){
    for(int i=0;i<3;i++) {
        scanf("%d",&arr[i]);
        T+=arr[i];
    }
    sort(arr,arr+3);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(arr[0],arr[1]));
}

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

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

[난이도] Gold5
[유형] DP

[풀이]
전형적인 배낭 문제입니다.
물건을 여러개를 선택할 수 있기 때문에
두번째 for문에서 for(int j=m;j>=0;j--) 이 아닌 for(int j=0;j<=m;j++) 를 사용하여
물건이 여러개 중복될 수 있도록 해야합니다.

또한 float을 100을 곱해 정수로 변환시 부동소수점 문제로 정확하지 않은 값으로 변환 될 수 있으므로
0.5를 더해주어야 합니다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,dp[10001],cal[5000],price[5000];
int main(){
    while(1){
        float f;
        scanf("%d%f",&n,&f);
        if(n==0) break;
        m=f*100+0.5;
        for(int i=0;i<n;i++) {
            scanf("%d%f",&cal[i],&f);
            price[i]=100*f;
        }
        memset(dp,0,sizeof(dp));
        int ans=0;

        for(int i=0;i<n;i++){
            for(int j=1;j<=m;j++){
                if(j-price[i]>=0) {
                    dp[j] = max(dp[j],dp[j-price[i]]+cal[i]);
                    ans=max(ans,dp[j]);
                }
            }
        }
        printf("%d\n",ans);
    }
}

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