백준 2758 로또 (C++)

https://www.acmicpc.net/problem/2758

#include <iostream>
#include <vector>

using namespace std;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin >> t;

    while (t--) {

        int n, m;
        long long ans = 0;
        cin >> n >> m;


        //dp[i][j]: 마지막으로 선택한 수가 j인 i개의 로또 번호
        vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0));


        for (int i = 1; i <= m; i++) {
            dp[1][i] = 1;
        }
        for (int k = 2; k <= n; k++) {
            for (int i = 1; i * 2 <= m; i++) {
                for (int j = i * 2; j <= m; j++) {
                    dp[k][j] += dp[k - 1][i];
                }
            }
        }

        for (int i = 1; i <= m; i++) {
            ans += dp[n][i];
        }
        cout << ans << '\n';
    }


    return 0;
}

1. 문제

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

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 n과 m으로 이루어져 있다.

출력

각 테스트 케이스에 대해 선영이가 로또를 몇 개나 구매하는지 한 줄에 하나씩 출력한다.

2. 풀이

        //dp[i][j]: 마지막으로 선택한 수가 j인 i개의 로또 번호
        vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0));

위와 같이 메모이제이션 배열을 설정한다고 하자. 

        for (int i = 1; i <= m; i++) {
            dp[1][i] = 1;
        }

마지막 숫자가 i인 1개의 로또 번호는 i를 번호로 선택하는 경우 한 가지 뿐이므로 위와 같이 초기화할 수 있다.

        for (int k = 2; k <= n; k++) {
            for (int i = 1; i * 2 <= m; i++) {
                for (int j = i * 2; j <= m; j++) {
                    dp[k][j] += dp[k - 1][i];
                }
            }
        }

이전에 고른 수보다 적어도 두 배가 되는 수를 선택하는 조건이 붙어있다. i를 이전의 마지막 수, j를 이후에 붙일 수라 정하면 j는 i의 두 배부터 시작하고, 문제의 조건에 따라 m 이하여야 한다. 이러면 k개의 수의 로또 번호를 정하는 경우는 k-1개의 i로 끝나는 로또 번호에 j를 붙이는 경우이다. 따라서 위와 같은 점화식을 세울 수 있다.

        for (int i = 1; i <= m; i++) {
            ans += dp[n][i];
        }
        cout << ans << '\n';

n개의 수를 뽑는 것이 문제이므로, n개의 수를 뽑는, 모든 경우를 더하여 출력하면 정답을 구할 수 있다.