BOJ 2758 : 로또 [C++]

 

2758번: 로또

 

무식하게 경우의 수를 다 세어보려다가 시간 초과

 

곰곰이 생각해 보다가 DP인 것 같아서 DP로 접근

 

로또에서 나올 수 있는 최대 숫자 2000, 뽑는 수의 개수 최대 10개 경우의 수를 DP로 구하기 위해

DP[i][j] = 숫자 j개를 뽑는데, 마지막 수가 i인 경우를 나타냈다.

 

DP[10][3]이라면 숫자 3개를 뽑는데, 마지막 수가 10인 경우이다

 

DP[10][3]은 어떻게 구할 수 있을까?

마지막(세 번째)에 10이 와야 하므로 2번째 숫자는 5 이하의 수만 올 수 있다. 

그러니 숫자 두 개를 뽑는데 마지막 숫자가 5이하인 경우를 모두 더하면 된다

 

DP[10][3] = DP[1][2] + DP[2][2] + DP[3][2] + DP[4][2] + DP[5][2]

 

    for (int i = 1; i < 2001; i++) {
        for (int j = 1; j < 11; j++) {
            if (j == 1) {
                dp[i][j] = 1;
                continue;
            }
            if (i < std::pow(2, j - 1)) {
                break;
            }
            for (int k = 1; k < i / 2 + 1; k++) {
                dp[i][j] += dp[k][j - 1];
            }
        }
    }

 

최악의 경우 2000 * 10 * 1000번 연산이 일어나고, 1억 번 이하이기 때문에 시간 내에 가능하다 생각한다

 

주의할 점은 long long으로 DP 배열을 구성하고, 정답을 구할 때도 long long을 사용해야 한다.

 

코드

#include <iostream>
#include <math.h>

int T, N, M;
long long dp[2001][11];

int main() {
    std::cin >> T;

    for (int i = 1; i < 2001; i++) {
        for (int j = 1; j < 11; j++) {
            if (j == 1) {
                dp[i][j] = 1;
                continue;
            }
            if (i < std::pow(2, j - 1)) {
                break;
            }
            for (int k = 1; k < i / 2 + 1; k++) {
                dp[i][j] += dp[k][j - 1];
            }
        }
    }

    for (int t = 0; t < T; t++) {
        std::cin >> N >> M;

        long long sum = 0;
        for (int i = 1; i < M + 1; i++) {
            sum += dp[i][N];
        }
        std::cout << sum << "\n";
    }

    return 0;
}