[백준 C++] 2758번 로또

2758번: 로또

문제 요약

문제

선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 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으로 이루어져 있다.
• 출력: 각 테스트 케이스에 대해 선영이가 로또를 몇 개나 구매하는지 한 줄에 하나씩 출력한다. ``` 예제1

입력 1 4 10 출력 4

## 풀이
이차원 dp를 사용한다. 숫자의 길이와 마지막 수를 각각 축으로 한다. 이때 다음 숫자는 전 숫자의 2배 이상만 될 수 있으므로 누적합으로 가능한 수들을 모두 구해둔다. 이때 뒤에서부터 누적합을 사용하면 더 편리하게 접근 할 수 있다. 

## 어려웠던 점


## 배운 점 / 느낀 점


## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int T, n, m;

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

    cin >> T;
    for(int _ = 0; _ < T; _++){
        cin >> n >> m;
        long long s = 0l;
        vector<vector<long long>> dp(m+1, vector<long long>(n));
        for (int i = 1; i <= m; i++) {
            dp[i][0] = 1;
        }
        for(int i = 1; i < n; i++){
            vector<long long> sss(m+1);
            sss[m] = dp[m][i-1];
            for(int j = m-1; j > 0; j--){
                sss[j] = sss[j+1] + dp[j][i-1];
                if(j*2 <= m){
                    dp[j][i] = sss[j*2];
                }
            }
        }
        for (int i = 1; i <= m; i++) {
            s += dp[i][n-1];
        }
        cout << s << '\n';
    }

    return 0;
}