문제

문제 링크

어떻게 접근할 것인가

  • 이 문제 쫌 까다로웠다.
  • 서쪽에 있는 위치에서 놓을 수 있는 각 지점의 개수를 하나씩 차곡차곡 저장해서 갯수를 센다.
  • 만일 서쪽 첫 위치에서 갈 수 있는 경우의 수가 3이면 3을 저장하고 다음 위치에 1부터 3까지 위치의 개수를 추가한다.

코드

#include <cstdio>
#include <vector>

using namespace std;

int t, a, b;

int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d %d", &a, &b);
        vector<vector<int> > arr(a+1, vector<int>(31, 0));
        arr[0][b - a + 1]++; 
        for(int i = 0; i < a; i++){
            for(int j = 0; j < 31; j++){
                if(arr[i][j] != 0){
                    for(int k = 1; k <= j; k++)arr[i+1][k] += arr[i][j];
                }
            }
        }
        int sum = 0;
        for(int i = 0; i < 31; i++)sum += arr[a][i];
        printf("%d\n", sum);
    }
}

느낀점

  • 풀어 낸 게 대견하다.