[백준] 1256 사전

문제 주소 : www.acmicpc.net/problem/1256

1256번: 사전

문제 확인

 

dp로 풀어도 되지만 a를 둔 후 z를 분배하는 식으로 중복 조합을 이용해 풀 수 있습니다.

 

풀이

 

a를 두고 z를 분배하는 식으로 점화식을 짜봅니다.

예를 들어 a : 3, z : 4 일 경우

_a_a_a_ 로 두고 z를 분배할 수 있는 공간은 4칸이 됩니다. 따라서 총경우의 수는 a+1 H z로 35가지가 나옵니다. 문제의 조건에 따라 k가 35 보다 높은 경우 -1을 출력해 예외처리를 해 줍니다.

 

z를 분배하는 식은 z의 개수에 따라 경우의 수가 일정하지 않으며 단순히 숫자로 구간을 나누게 되면 틀립니다. 따라서 구간을 nHr 식에 대입하여 구해야 하며 사용한 z의 개수에 따라 다음 구간에 반영해 주어야 합니다.

_a_a_a_ 에서 첫 칸에 z를 하나 두는 경우 : za_a_a_ 가 되며 남은 칸 수는 3, z의 수는 3이 됩니다.

차례대로 구해보면 다음과 같습니다.

a_a_a_ : 칸=3, z=4 => 3H4 = 15

za_a_a_ : 칸=3, z=3 => 3H3 = 10

zza_a_a_ : 칸=3, z=2 => 3H2 = 6

zzza_a_a_ : 칸=3, z=1 => 3H1 = 3

zzzza_a_a_ : 칸=3, z=0 => 3H0 = 1

 

따라서 점화식을 다음과 같이 세울 수 있습니다.

칸 = n, z = r 상황에서 가질 수 있는 경우의 수 : nHr, 현재 칸에 둘 수 있는 z의 개수는 남은 k 값과 가장 가까운 nHr의 총 합이 됩니다.

위와 같은 예시에서 k가 15 이하인 경우 앞에 z를 둘 수 없으며 16~25 인 경우 za_ ..., 26~31 : zza_... 이런 식으로 나아가면 됩니다.

 

다음 루프로 오게 되면 a를 하나 썼으므로 칸 수 n은 1 줄게 되며 z는 그전 구간에서 사용하고 남은 z의 수가 되고 이 과정을 반복하면 됩니다.

 

주의해야 할 점은 a, z의 개수가 크면 nHr 값이 너무 커지므로 k값의 최대인 1,000,000,000 이상일 때 예외처리를 해 주어야 합니다.

 

코드

#include <cstdio>
 
long long nCr(int n, int r) {
    if (r > n - r) r = n - r;
    long long ans = 1;
    int i;
    for (i = 1; i <= r; i++) {
        ans *= n - r + i;
        ans /= i;
        if (ans > 1000000000 || ans < 0)
            return -1;
    }
    return ans;
}
 
int main() {
    int n, r;
    long long k;
    scanf("%d%d%lld", &n, &r, &k);
    long long t = nCr(n + r, r);
 
    if (t == -1 || k <= t) {
        k--;
        for (; k; n--) {
            for (int j = r; j >= 0; j--) {
                long long t = nCr(n + j - 1, j);
                if (t == -1)
                    break;
                if (t <= k) {
                    k -= t;
                    r = j - 1;
                    printf("z");
                }
                else
                    break;
            }
            printf("a");
        }
        while (n--)
            printf("a");
        while (r--)
            printf("z");
    }
    else
        printf("-1");
}