[백준] 2248번-(Python 파이썬) - DP

문제링크 : https://www.acmicpc.net/problem/2248

이번 문제에서 n자리의 2진수와 그 중 1인 비트가 m개 존재할 때의 점화식은
(N, M) = (N-1, M) + (N-1, M-1) 가 된다.

N, L, I = map(int, input().split())
dp = [[0] * 32 for _ in range(32)]

#dp 테이블에 저장
for i in range(31):
    dp[0][i] = 1
for i in range(1, 32):
    dp[i][0] = dp[i-1][0]
    for j in range(1, 32):
        dp[i][j] = dp[i-1][j] + dp[i-1][j-1]

#출력
for n in range(N, 0, -1):
    if I <= dp[n-1][L]:
        print('0', end="")
    else:
        print('1', end="")
        I -= dp[n-1][L]
        L -= 1