[DP, 조합론] BOJ 1256 사전 (C++)

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

1256번: 사전

 

문제 해결 알고리즘

 

다이나믹 프로그래밍으로 푸는 문제

 

next_permutation으로 일일히 순서대로 구하면 K가 최대 10억이기 때문에 시간초과를 받는다.

 

a문자의 개수와, z문자의 개수로 이중배열을 선언해준다.

 

dp[a문자의 개수][z문자의 개수] = dp[a문자의 개수 - 1][z문자의 개수] + dp[a문자의 개수][z문자의 개수-1] 

 

위의 식대로 dp배열을 만들어주고

 

K가 a가 하나 적은 dp값보다 크다면 z를 출력하고 K값은 a가 하나 적은 dp값에서 빼준다. M도 1 감소

 

K가 a가 하나 적은 dp값보다 작거나 같다면 a를 출력해주고 N을 1 감소

while(N!=0 && M!=0){
        if(dp[N-1][M] < K){
            cout << 'z';
            K -= dp[N-1][M--];
        }
        else{
            cout << 'a';
            N--;
        }
    }

그 후 나머지 a나 z 출력해준다.

 

여기서 K의 최대가 10억이고 N과 M이 최대 100이기 때문에 long long 자료형에도 벗어나게 되는 경우가 생긴다.

그렇기 때문에 dp값이 10억이 넘어가게 된다면 10억으로 dp값을 매겨준다.

 

소스 코드

 

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

const ll MAX = 1000000000;
ll dp[101][101];

int main(){
    ll N, M, K; cin >> N >> M >> K;

    for(int i=0;i<=100;i++) dp[0][i] = dp[i][0] = 1;
    for(int i=1;i<=100;i++) dp[1][i] = dp[i][1] = i+1;

    for(int i=2;i<=N;i++){
        for(int j=2;j<=M;j++){
            if(MAX < dp[i-1][j] + dp[i][j-1]) dp[i][j] = MAX;
            else dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }

    if(dp[N][M] < K) {
        cout << -1;
    }
    else{
        
        while(N!=0 && M!=0){
            if(dp[N-1][M] < K){
                cout << 'z';
                K -= dp[N-1][M--];
            }
            else{
                cout << 'a';
                N--;
            }
        }
        
        if(N != 0){
            for(int i=0;i<N;i++) cout << 'a';
        }
        else if(M != 0){
            for(int i=0;i<M;i++) cout << 'z';
        }
    
    }

}