[BOJ] 백준 1256 사전

문제 링크

www.acmicpc.net/problem/1256

1256번: 사전

 

풀이

처음부터 예시를 들어 시뮬레이션해봅시다.

모든 과정이 자릿수만 다르지 똑같은 원리로 돌아갑니다.

$n = 3, m = 2, k = 3$인 경우를 예로 들어보겠습니다.

 

1. 정답 구하기

step 1)

첫자리 알파벳을 우선 $a$로 결정한다고 가정합니다.

이때 가능한 문자열은 파랗게 칠한 6가지 문자열입니다. 

$aaabb$

$aabab$

$aabba$

$abaab$

$ababa$

$abbaa$

$baaab$

$baaba$

$babaa$

$bbaaa$

 

우리가 찾는 3번째 문자열은 저 6개의 문자열 안에 있으므로 첫자리를 $a$로 잡아야 하는 걸 알 수 있습니다.

그리고 더 이상 $b$로 시작하는 문자열은 생각하지 않아도 됩니다.

 

step 2)

두 번째 자리 알파벳을 $a$로 결정한다고 가정합시다.

이때 가능한 문자열은 3가지의 파란색 문자열입니다.

$aaabb$

$aabab$

$aabba$

$abaab$

$ababa$

$abbaa$

 

우리는 3번째 문자열을 찾고 있으니 두 번째 자리도 $a$로 채워야 합니다. 마찬가지로 아래 3개의 문자열은 생각하지 않아도 됩니다.

 

step 3)

세 번째 자리 역시 $a$라고 가정합시다.

$aaabb$

$aabab$

$aabba$

 

이때 가능한 문자열은 하나인데, 우리는 3번째 문자열을 찾고 있습니다.

그럼 여기서 세 번째 자리가 $a$인 파란색 문자열을 버리고, 아래 두 가지 문자열 중에서 찾아주면 됩니다.

하나를 버렸으니 다음부턴 남은 문자열 중 (3 - 1)번째 = 2번째 문자열을 찾아야 합니다.

 

step 4)

네 번째 자리를 $a$라고 가정하면 하나의 문자열만 남습니다.

step 3과 마찬가지로 네 번째 자리가 $a$인 하나의 문자열을 버리고, 나머지 중 (2 - 1)번째 = 1번째 문자열을 찾아줍니다.

$aabab$

$aabba$

 

step 5)

$aabba$ 

다섯 번째 자리를 $a$라고 가정하고, 그 안에서 1번째 문자열을 찾았습니다.

 

 

 

2. 남은 자리의 가능한 문자열 조합을 구하는 방법

정답을 구하는 과정 자체는 위의 시뮬레이션대로 구현하면 됩니다.

추가로 고려해야 할 것은 다음 두 가지입니다.

 

1) $i$번 자리를 $a$로 고정했을 때 남은 자리에 올 수 있는 문자열의 가짓수

→ DP로 조합(Combination)을 구해놓으면 해결할 수 있습니다.

현재 상황에서 남아있는 $a$의 개수가 $n$, 남아있는 $b$의 개수가 $m$이라고 합시다. $i$번 자리를 $a$로 고정했으므로 $n-1$, $m$개가 각각 남게 됩니다.

($(n-1+m)$개 자리 중 $a$를 배치하는 경우의 수) * (남은 자리에 $b$를 배치하는 경우의 수)

$= {}_{n-1+m} \mathrm{ C }_{n-1} \cdot {}_{m} \mathrm{ C }_{m}$

$= {}_{n-1+m} \mathrm{ C }_{n-1}$

을 쉽게 구할 수 있습니다.

 

2) ${}_{n} \mathrm{ C }_{m}$이 너무 큼

만약 $n = 100$, $m = 100$ 이면${}_{200} \mathrm{ C }_{100}$을 구해야 하는데, 수가 너무 큽니다. long long 범위도 한참 초과합니다.

근데 문제의 조건에서 $K \leq 1,000,000,000$임을 알 수 있습니다. 시뮬레이션 과정 중에 $k \leq $(조합의 수)인 경우를 확인해주었잖아요? 그러니까 조합의 수가 10억 이상이면 정확한 값을 알 필요 없이 적당히 큰 값으로만 비교해주어도 됩니다.

조합을 구할 때 값이 10억이 넘는 값을 적당한 INF로 설정해주어 해결하도록 합니다.

 

시뮬레이션에 관한 코드는 line 18 ~ 26에 있으니 참고하시면 되겠습니다.

 

정답 코드

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
ll d[444][222];

ll comb(int n, int r) {
    if (n == r || r == 0) return 1;
    ll &ret = d[n][r];
    if (ret != -1) return ret;
    ll val = comb(n - 1, r - 1);
    ll val2 = comb(n - 1, r);
    if (val + val2 > 1'000'000'000) return ret = INF;
    return ret = val + val2;
}

void go(int n, int m, ll rest) {
    if (ll c = comb(n + m - 1, n - 1); n > 0 && rest <= c) {
        cout << 'a';
        go(n - 1, m, rest);
    } else if (m > 0) {
        cout << 'z';
        go(n, m - 1, rest - c);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(d, -1, sizeof(d));
    int n, m;
    ll k;
    cin >> n >> m >> k;
    if(comb(n+m, n) < k){
        cout << -1;
        return 0;
    }
    go(n, m, k);
}