[BOJ] 로또 2758

in prog on Dp, 백준
[BOJ] 로또 2758

BOJ 로또 2758

로또 2768

문제 설명

선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 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이 주어졌을 때, 선영이가 구매하는 로또의 개수를 출력하는 프로그램을 작성하시오.

(조건: n ≤ 10, m ≤ 2000)

풀이

이전에 고른 수보다 적어도 2배가 되도록 고른다.

1을 고르면 적어도 2, 2를 고르면 적어도 4… 이렇게 한 없이 커지는 문제는 오히려 큰 수에서 시작해서 거꾸로 1까지 도달하면 좀 더 쉽게 접근할 수 있다. 관점을 바꿔서 큰 수부터 골라보자.

만약 선영이가 맨 처음 m이라는 숫자를 골랐다면 앞으로 m//2 이하의 숫자 중 n-1개의 수를 골라야 한다.

그렇다면 j 이하의 숫자 중 i개의 숫자를 고르는 경우의 수는

j를 패스하고 j-1 이하의 숫자 중 i개 + j를 고르고 j//2 이하의 숫자 중 i-1개를 고르는 경우를 합친 가지수가 될 것이다.

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]
전체 답안
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])

마무리

DP는 점화식을 알면 구현은 간단한데… 역시나 규칙 찾는 것이 정말 어려운 것 같다.

규칙을 찾는 연습을 많이 해보자!