사전 C++ - 백준 1256

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

DP 문제.

역추적에 관한 지식을 더해준 문제이다.

문제 접근

$N,M$ 의 범위가 낮아 $NM$ DP 일거라고 예상하고

끼워 맞추고 $DP[i][j]$ 를 $i,j$ 까지 봤을 때 경우의 수라고 두었다.

DP 테이블을 그리고 봤더니 점화관계는

$DP[i][j]=DP[i-1][j]+DP[i][j-1]$ 이었다.

경우의 수를 무턱대고 구하긴 했는데 문자열은 어떻게 구할까?

이때 역추적과 비슷한 과정이 필요하다.

$DP[i-1][j]$의 의미는 $a\;i-1개,\;z\;j개$가 있을 때의 경우의 수라고도

볼 수 있는데 $DP[i][j]$와 함께 보면 더 중요한 의미가 있다.

바로 $a$를 앞자리에

(뒷자리도 가능하다. 단, 고정시키는 위치는

연속적이어야 한다. 따라서 앞자리 혹은 뒷자리이다.)

고정시켰을 때의 경우인 것이다.

마찬가지로 $DP[i][j-1]$은 $z$를 고정시켰을 때의 경우이다.

$k$가 $DP[i-1][j]$보다 작거나 같다면 앞자리에

$a$를 고정시켜야겠고, 아니면 $z$를 고정시켜야 한다.

$z$를 고정시킬 때에는 앞 경우를 빼고 생각해주어야 하기 때문에,

$DP[i-1][j]$를 빼고 진행해주면 된다.

코드는 다음과 같다.

#include <bits/stdc++.h>
#define INF 1000000000
typedef long long ll;
using namespace std;

int dp[101][101];
int n,m,k;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> m >> k;
    for(int i=1;i<=n;i++) dp[i][0]=1;
    for(int i=1;i<=m;i++) dp[0][i]=1;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) dp[i][j]=min(dp[i-1][j]+dp[i][j-1],INF);
    if(dp[n][m]<k){
        cout << -1;
        return 0;
    }
    int a=n,z=m;
    while(a!=0 || z!=0){
        if(a==0){
            cout << 'z';
            z--;
            continue;
        }
        if(z==0){
            cout << 'a';
            a--;
            continue;
        }
        if(dp[a-1][z]>=k){
            cout << 'a';
            a--;
        }
        else{
            cout << 'z';
            k-=dp[a-1][z];
            z--;
        }
    }
    return 0;
}