프로그래밍

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