[백준 2758번] 로또 (python)

문제

선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 1부터 m까지 숫자 중에 n개의 수를 고르는 로또이다.

이렇게 열심히 로또를 하는데, 아직까지 한 번도 당첨되지 않은 이유는 수를 고를 때 각 숫자는 이전에 고른 수보다 적어도 2배가 되도록 고르기 때문이다.

예를 들어, n=4, m=10일 때, 선영이는 다음과 같이 고를 수 있다.

• 1 2 4 8
• 1 2 4 9
• 1 2 4 10
• 1 2 5 10

따라서 선영이는 로또를 4개 산다. 

선영이는 돈이 엄청나게 많기 때문에, 수를 고르는 방법의 수 만큼 로또를 구매하며, 같은 방법으로 2장이상 구매하지 않는다.

n과 m이 주어졌을 때, 선영이가 구매하는 로또의 개수를 출력하는 프로그램을 작성하시오.

 

기록

(dp 14일차) 방법만 알면 구현은 간단했던 문제!

 

먼저, dp[i][j]에는 j 이하의 i개 수를 만드는 방법 개수를 저장한다. 점화식은 dp[i][j]를 계산한다고 할 때, j-1 이하의 i개 수를 만드는 방법(j를 사용하지 않고 i개 수를 만드는 방법)+ j//2 이하의 i-1개 수를 만드는 방법(j를 사용하여 i개 수를 만드는 방법)을 사용한다. 예를들어 10 이하 4개 수로 로또번호를 만든다고 할 때, 9 이하의 4개 수를 만드는 방법(1 2 4 8, 1 2 4 9)과 5 이하의 3개를 만드는 경우(1 2 4 (10), 1 2 5 (10))를 더하여 4개로 계산된다.

 

코드

dp = [[0]*2001 for i 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]

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

1.  j 이하의 i개 수를 만드는 방법 개수를 저장할 dp 배열을 생성한다. (모든 테스트케이스에 사용할 수 있도록 n, m의 최대 수로 크기 설정)

2. dp 배열의 0번째를 1로 초기화 한다. (0~2001 이하의 0개 수로 로또번호를 만드는 방법은 1가지!)

3. 위에서 설명한 dp[i][j] = dp[i][j-1]+dp[i-1][j//2] 점화식을 사용하여 배열을 채운다.

4. 각 테스트케이스에서 원하는 값을 dp 배열에서 찾아 출력