[백준][Python] 2758 로또

제한된 선택지에서 선택하는 문제는 dp로 접근하자

 

import sys
input = sys.stdin.readline

dp = [[1 if j==0 else i if j==1 else 0 for i in range(2001)] for j in range(15)]
# j가 0일때 1이고 아니면 i인데 j가 1일때 i 고 아니면 0이다.
for i in range(2,15):
    for j in range(1,2001):
        dp[i][j] = dp[i-1][j//2] + dp[i][j-1]

for _ in range(int(input())):
    n,m = map(int,input().split())
    sys.stdout.write(str(dp[n][m]) +'\n')