[백준] 1256: 사전

0. 문제 주소

 

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

1256번: 사전

 

 

1. 풀이

 

소문자를 대문자로 써놔서 근데 또 돌아가서 시간만 날린 문제...지만 좋은 문제

 

 

가장 먼저 필요한 건 i 개의 a와 j 개의 z로 만들 수 있는 단어의 개수를 저장할 2차원 dp 테이블이다.

 

단순하게 (i+j) ! / ( i ! ) ( j ! ) 으로 계산할 수 있지만 당연히 오버플로우가 나기 때문에, dp를 이용한다.

 

K의 값이 10억 이하이므로, 그 이상은 오버플로우 처리를 위해 값이

10억을 초과하면 10억 + 1의 값을 갖게 전처리해준다.

 

    for (ll i=0LL;i<=N;i++){
        for (ll j=0LL;j<=M;j++){
            if (i==0 || j==0) dp[i][j] = 1LL;
            else{
                dp[i][j] = dp[i][j-1] * (i+j) / j > MAX ? MAX + 1LL : dp[i][j-1] * (i+j) / j;
            }
        }
    }

 

 

 

다음으로 각 자리에 a를 넣어야 되느냐, z를 넣어야 되느냐를 재귀적으로 결정해주는 함수를 다음과 같이 작성한다.

 

void solve(ll n, ll m, ll remain){
    if (n == 0){
        for (int i=0;i<m;i++){
            answer += 'z';
        }
        return;
    }
    else if (m == 0){
        for (int i=0;i<n;i++){
            answer += 'a';
        }
        return;
    }

    if (dp[n-1][m] >= remain){
        answer += 'a';
        solve(n-1, m, remain);
    }
    else{
        answer += 'z';
        solve(n, m-1, remain - dp[n-1][m]);
    }

    return;
    
    // remain : 앞으로 남은 순번
    // dp[n-1][m] : 이번에 a를 넣었을 때,
    // 그 뒤에 나머지 a와 z로 만들 수 있는 단어의 경우의 수
    // dp[n-1][m] >= remain : 이번에 a를 넣어도
    // 뒤에 만들 수 있는 경우의 수가 충분히 남아 있음
}

 

첨부한 주석을 보면 쉽게 이해할 수 있다.

 

단어들을 사전 순으로 쭉 나열했을 때, 다음과 같이 두 부분으로 나눌 수 있다.

 

 

|| 맨 앞 자리가 a인 단어들 |||| 맨 앞자리가 z인 단어들 ||

 

 

이 때 목표 순번까지 남은 순번이 앞에서부터 셌을 때 |||| 이 라인을 넘는다면, 맨 앞자리는 z가 되어야 할 것이고,

 

다음 재귀 단계에 전해줄 남은 순번은

 

(이번 단계에서 남았던 순번 - 맨 앞자리가 a인 단어들의 개수) 일 것이다.

 

이 부분이 바로 

 

    if (dp[n-1][m] >= remain){
        answer += 'a';
        solve(n-1, m, remain);
    }
    else{
        answer += 'z';
        solve(n, m-1, remain - dp[n-1][m]);
    }

 

이다.

 

2. 풀이 코드

 

* 유의할 점

0. 빡친 상태로 디버깅 하느라 코드가 지저분하다

1. 오버플로우 주의

 

#include <bits/stdc++.h>
#define MAX 1000000000LL
#define ll long long

using namespace std;

ll N, M, K;
ll dp[101][101];
string answer;

void solve(ll n, ll m, ll remain){
    if (n == 0){
        for (int i=0;i<m;i++){
            answer += 'z';
        }
        return;
    }
    else if (m == 0){
        for (int i=0;i<n;i++){
            answer += 'a';
        }
        return;
    }

    if (dp[n-1][m] >= remain){
        answer += 'a';
        solve(n-1, m, remain);
    }
    else{
        answer += 'z';
        solve(n, m-1, remain - dp[n-1][m]);
    }

    return;
    // remain : 앞으로 남은 순번
    // dp[n-1][m] : 이번에 a를 넣었을 때,
    // 그 뒤에 나머지 a와 z로 만들 수 있는 단어의 경우의 수
    // dp[n-1][m] >= remain : 이번에 a를 넣어도
    // 뒤에 만들 수 있는 경우의 수가 충분히 남아 있음
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> N >> M >> K;

    for (ll i=0LL;i<=N;i++){
        for (ll j=0LL;j<=M;j++){
            if (i==0 || j==0) dp[i][j] = 1LL;
            else{
                dp[i][j] = dp[i][j-1] * (i+j) / j > MAX ? MAX + 1LL : dp[i][j-1] * (i+j) / j;
            }
        }
    }

    if (K > dp[N][M]){
        cout << "-1\n";
        return 0;
    }

    solve(N, M, K);
    cout << answer << "\n";


}