[백준] 2758 로또

문제

• 1~m 까지 숫자 중에서 n개의 수를 고르는 로또가 있다.
• 선영이는 각 숫자를 고를 때 이전에 고른 수보다 적어도 2배가 되도록 고른다.
• n과 m이 주어졌을 때 선영이가 구매하는 로또의 개수 구하기

 

• 1 <= n <= 10
  1 <= m <= 2000

 

풀이

• T 케이스 만큼 반복되는데, n과 m의 범위가 작으므로 한 번에 구해두고 바로 값을 출력하도록 한다.
•  dp[n][m] : n번째 자리가 m일 때 로또 개수
  dp[n][m] = dp[n][m-1] + dp[n-1][m//2]
  -> (m이 마지막 수가 아닐 때 + m이 마지막 수일 때)
  -> n번째 자리가 ~m-1인 경우의 수 + n-1번째 자리가 ~m//2 이고 마지막 수가 m인 경우의 수

 

# dp[n][m] : n번째 자리가 m일 때 로또 개수
dp = [[0]*2001 for _ in range(11)]
dp[0] = [1] * 2001

for i in range(1, 11) :
    for j in range(1, 2001) :
        dp[i][j] = dp[i][j-1] + dp[i-1][j//2]

for _ in range(int(input())) :
    N, M = map(int, input().split())
    print(dp[N][M])

 

References

• 백준 DP