[파이썬] 백준 2758: 로또 (골드4)

[파이썬] 백준 2758: 로또 (골드4)

2758번: 로또

---

문제

---

풀이

0. 방향성 생각

• 2차원 DP : dp[n번째 자리가][m으로 끝나는 경우의 수]

1. 전체 코드

dp = [[0]*2001 for _ in range(11)]
dp[1] = [0]+[1]*2000
for n in range(1,10):
    for x in range(2001):
        if x//2:
            dp[n+1][x] += sum(dp[n][:x//2+1])

for _ in range(int(input())):
    n,m = map(int,input().split())
    print(sum(dp[n][:m+1]))

 

코멘트

부분합쓰면 시간 더 줄일 수 있을듯