백준 22985 문자열 조작의 달인

http://www.acmicpc.net/problem/22985 

22985번: 문자열 조작의 달인

DP문제였습니다. 처음에는 조합론문제일줄 알았는데 문자열에 변화를 가할떄 'z'에도 변화를 가할 수 있으므로 중복조합으로 풀 수 없다는 걸 알고 DP로 풀었습니다. 

최대 변화 횟수는 10^18이지만 나올 수 있는 문자열 자체는 한정되어있다는걸 알 수 있습니다. 

길이가 최대 300인 문자열에 변화를 줄 수 있는 최대횟수는 전부 'a'로 이루어졌다고 가정해도 25*300이 최대입니다. 따라서 우리는 주어진 문자열에서 가할 수 있는 최대 변화회수를 구하고 거기에 맞추면 됩니다. 

 

DP로 문자열의 상태를 구할때 주의해야될점은 z에 변화를 가할 수 있다는점입니다. DP배열 차원을 하나 더 늘려 현재 문자열의 상태에 'z'가 들어가 있는 가짓수와 나머지를 따로 구해야합니다.

 

또한 답을 구할때 문제에서 주어진 변화횟수 이하에서도 'z'가 들어가있으면 z에 변화를 가해 증가 시킬수 있으므로 전부 더해주면됩니다.

#include<stdio.h>
#include<queue>
#include<vector>
#include<iostream>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
long long mod=1e9+7LL;
long long dp[301][8000][2];
int main(){
    long long N,M;
    cin>>N>>M;
    string input;
    cin>>input;
    long long k=0;
    for(auto i : input){
        k+='z'-i;
    }
    M=min(k,M);
    for(int x=input[0];x<='z';x++){
        int now=x-input[0];
        if(x=='z'){
            dp[0][now][1]=1;
        }
        else{
            dp[0][now][0]=1;
        }
    }
    for(int x=1;x<N;x++){
        for(int y=0;y<8000;y++){
            if(dp[x-1][y][0]){
                for(int z=input[x];z<='z';z++){
                    int now=z-input[x];
                    if(z=='z'){
                        dp[x][y+now][1]=(dp[x][y+now][1]+dp[x-1][y][0])%mod;
                        continue;
                    }
                    dp[x][y+now][0]=(dp[x][y+now][0]+dp[x-1][y][0])%mod;          
                }
            }
            if(dp[x-1][y][1]){
                for(int z=input[x];z<='z';z++){
                    int now=z-input[x];
                    dp[x][y+now][1]=(dp[x][y+now][1]+dp[x-1][y][1])%mod;          
                }
            }
        }
    }
    long long solve=dp[N-1][M][0];
    for(int x=M;x>=0;x--){
        solve=(solve+dp[N-1][x][1])%mod;
    }
    cout<<solve;
}