점화식을 통한 정답 추적

코드

#include <stdio.h>
#include <memory.h>

typedef long long int lld;

int n, l;
lld dp[33][33], i;
char p[60];

int go(int pos, int cnt) {
    lld &ret = dp[pos][cnt];

    if (pos >= n) {
        if (cnt > l)
            return ret = 0;
        return ret = 1;
    }
    if (ret >= 0)
        return ret;

    return ret = go(pos + 1, cnt) + go(pos + 1, cnt + 1);
}

void go2(int pos, int cnt, lld k) {
    lld mid = dp[pos + 1][cnt];

    if (mid < 0)
        return;
    if (mid >= k) {
        p[pos] = '0';
        go2(pos + 1, cnt, k);
    }
    else {
        p[pos] = '1';
        go2(pos + 1, cnt + 1, k - mid);
    }
}

int main()
{
    memset(dp, 0x80, sizeof(dp));
    scanf("%d%d%lld", &n, &l, &i);
    go(0, 0);
    go2(0, 0, i);
    printf("%s", p);
    return 0;
}

https://www.acmicpc.net/problem/2248 풀이 코드

정리

관련문제

• https://www.acmicpc.net/problem/1023
• https://www.acmicpc.net/problem/2248

참고자료