프로그래밍

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

[난이도] Gold5
[유형] DP

[풀이]
DP[i] : s가 길이 n인 암호 문자열일 때, s[i..n-1] 로 만들 수 있는 해석의 총 개수.

#include <string>
#include <iostream>
#include <cstring>
using namespace std;
int dp[5001];
string s;
int sol(int n){
    if(n>=s.size()) return 1;
    int& ret = dp[n];
    if(ret!=-1) return ret;
    if(s[n]=='0') return 0;
    ret=sol(n+1);
    if(n+1<s.size()){
        int k = (s[n]-'0')*10+(s[n+1]-'0');
        if(k<27) ret=(ret+sol(n+2))%1000000;
    }
    return ret;
}
int main(){
    cin >> s;
    memset(dp,-1,sizeof(dp));
    cout << sol(0);
}

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

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

[난이도] Gold1
[유형] DP

[풀이]
dp[l][r] : s[l~r]가 팰린드롬이면 1, 아니면 0
dp2[i] : 문자열의 길이가 N일때, 부분문자 s[i~(N-1)] 에서 분할 개수의 최솟값

dp[2501][2501]을 dp를 이용해 구한 뒤,
이를 이용해 dp2[2501]도 dp로 구해주면 됩니다.

#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
string s;
int N,dp[2501][2501],dp2[2501];
int sol(int l,int r){
    if(l>=r) return 1;
    int& ret = dp[l][r];
    if(ret!=-1) return ret;
    if(s[l]==s[r]) ret=sol(l+1,r-1);
    else ret=0;
    return ret;
}
int sol2(int n){
    if(n==N) return 0;
    int& ret = dp2[n];
    if(ret!=-1) return ret;
    ret=9e8;
    for(int i=n;i<N;i++)
        if(dp[n][i]) ret=min(ret,1+sol2(i+1));
    return ret;
}
int main(){
    cin >> s;
    N=s.size();
    memset(dp,-1,sizeof(dp));
    memset(dp2,-1,sizeof(dp2));
    for(int i=0;i<s.size()-1;i++)
        for(int j=i+1;j<s.size();j++) sol(i,j);
    cout << sol2(0);
}

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

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

[난이도] Platinum5
[유형] DP

[풀이]
O(nlogn) LIS 문제입니다.

#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int N,mp[500001],pos[100001];
pair<int,int> a[100001];
set<int> ans;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        scanf("%d%d",&a[i].first,&a[i].second);
        ans.insert(a[i].first);
    }
    sort(a,a+N);
    for(int i=0;i<N;i++) mp[a[i].second]=i;

    vector<int> v;
    for(int i=0;i<N;i++){
        int idx = lower_bound(v.begin(),v.end(),a[i].second)-v.begin();
        if(v.size()==idx) v.push_back(a[i].second);
        else v[idx]=a[i].second;
        pos[i]=idx;
    }
    int k=v.size()-1;
    for(int i=N-1;i>=0;i--){
        if(pos[i]==k){
            ans.erase(a[i].first);
            if(--k<0) break;
        }
    }
    printf("%d\n",ans.size());
    for(auto k : ans) printf("%d\n",k);
}

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

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

[유형] DP

[풀이]
bitmask를 이용한 3차원 dp를 이용해 해결이 가능합니다.

dp[n][m][bit] : 맨 앞자리수가 m이면서, 길이가 n이고, bit에 mask된 숫자들을 사용한 숫자들의 개수

#include <cstdio>
#include <cstring>
using namespace std;
int N,dp[101][10][1<<10],mod=1e9;
int sol(int n,int m,int bit){
    if(n==N) return ((1<<m)|bit)==((1<<10)-1);

    int& ret = dp[n][m][bit];
    if(ret!=-1) return ret;
    ret=0;
    bit |= (1<<m);
    if(m-1>=0) ret=(ret+sol(n+1,m-1,bit))%mod;
    if(m+1<10) ret=(ret+sol(n+1,m+1,bit))%mod;
    return ret;
}
int main(){
    scanf("%d",&N);
    memset(dp,-1,sizeof(dp));
    int ans=0;
    for(int i=1;i<10;i++){
        ans+=sol(1,i,0);
        ans%=mod;
    }
    printf("%d",ans);
}

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

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

[난이도] Gold5
[유형] DP

[풀이]
3의 배수의 모든 자릿수의 합을 3으로 나눈 나머지는 0 이라는 성질을 알고 있어야 풀 수 있는 문제입니다.
15의 배수의 1의 자리수는 0또는 5인데 문제의 조건에 의해 1의 자리에는 5밖에 올수밖에 없습니다.
이를 만족하면서 위의 3의 배수의 성질을 만족하는 모든 수를 찾아주면 됩니다.

dp[i][j] : 자리수가 i이면서 각 자리수의 합을 3으로 나눈 나머지가 j인 수들의 개수

위와 같이 정의해주면 아래와 같은 점화식이 나옵니다.

dp[i][0]=(dp[i-1][1]+dp[i-1][2]); // (1+5)%3==0, (2+1)%3==0
dp[i][1]=(dp[i-1][2]+dp[i-1][0]); // (2+5)%3==1, (0+1)%3==1
dp[i][2]=(dp[i-1][1]+dp[i-1][0]); // (0+5)%3==2, (1+1)%3=002

최종적으로 dp[N][0]을 출력해주면 됩니다.

#include <cstdio>
int N,mod=1e9+7,dp[1600][3];
int main(){
    scanf("%d",&N);
    dp[2][0]=dp[2][1]=1;
    for(int i=3;i<=N;i++){
        dp[i][0]=(dp[i-1][1]+dp[i-1][2])%mod;
        dp[i][1]=(dp[i-1][2]+dp[i-1][0])%mod;
        dp[i][2]=(dp[i-1][1]+dp[i-1][0])%mod;
    }
    printf("%d",dp[N][0]);
}

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

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

[난이도] Gold2
[유형] DP

[풀이]
최솟값은 DP, 최댓값은 규칙성을 이용

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int tc,N;
long long dp[101]={0,0,1,7,4,2,6,8,10,};
int main(){
    cin >> tc;
    for(int i=9;i<101;i++){
        dp[i]=9e20;
        for(int j=2;j<=7;j++){
            long long v = dp[i-j]*10;
            if(j!=6) v+=dp[j];
            dp[i]=min(dp[i],v);
        }
    }
    while(tc--){
        cin >> N; 
        string maxv;
        cout << dp[N];
        if(N%2==0) {
            for(int i=0;i<N/2;i++) maxv+='1';
        }
        else{
            maxv+='7';
            for(int i=0;i<N/2-1;i++) maxv+='1';
        }
        cout << ' ' << maxv << '\n';
    }
}

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

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

[난이도] Gold2
[유형] DP

[풀이]
오름차순으로 되어있는 최대 길이 수열을 구한 뒤 이 값을 N에서 빼주면 됩니다.
이게 가능한 이유는
오름차순으로 되어있는 수들은 건드릴 필요가 없고,
오름차순으로 되어있지 않은 나머지 수들은 최소 한번씩은 움직여야 하기 때문입니다.

오름차순으로 되어있는 최대 길이 수열은 결국 유명한 증가하는 최대 부분 수열(LIS) 입니다.

이것은 DP로 구할 수 있습니다. N이 20만이기 때문에 O(NlogN) 알고리즘을 사용해서 구해주면 됩니다. 

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,a[200000];
vector<int> v;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    v.push_back(a[0]);
    for(int i=1;i<N;i++){
        auto idx = lower_bound(v.begin(),v.end(),a[i])-v.begin();
        if(idx<v.size()) v[idx]=a[i];
        else v.push_back(a[i]);
    }
    printf("%d",N-v.size());
}

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

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

[난이도] Gold2
[유형] DP

[풀이]
DP[y][x] : y,x에서 출발해서 미로에서 탈출 가능하면 1, 아니면 0

#include <cstdio>
#include <cstring>
using namespace std;
int N,M,ans,visit[501][501],dp[501][501],board[501][501],dy[4]={-1,0,1,0},dx[4]={0,1,0,-1};
int sol(int y,int x){
    visit[y][x]=1;
    int& ret =dp[y][x];
    if(ret!=-1) {
        visit[y][x]=0;
        return ret;
    }
    int d = board[y][x];
    int ny=y+dy[d],nx=x+dx[d];
    if(ny<0||nx<0||ny>=N||nx>=M) ret=1;
    else {
        if(visit[ny][nx]) ret=0;
        else ret = sol(ny,nx);
    }
    visit[y][x]=0;
    return ret; 
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++){
            char d;
            scanf(" %c",&d);
            if(d=='R') board[i][j]=1;
            else if(d=='D') board[i][j]=2;
            else if(d=='L') board[i][j]=3;
        }
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) {
            ans+=sol(i,j);
        }
    printf("%d",ans);
}

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