Problem 15 : Lattice paths (5%)

Description

original

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

grid

How many such routes are there through a 20×20 grid?

간략해석

위와 같은 2 × 2 격자의 왼쪽 위 모서리에서 출발하여 오른쪽 아래 모서리까지 도달하는 길은 모두 6가지가 있습니다 (거슬러 가지는 않기로 합니다).

그러면 20 × 20 격자에는 모두 몇 개의 경로가 있습니까?

Idea & Algorithm

naive idea

이 문제는 매우 유명한 조합 문제이자, DP 문제이다.

DP

각 칸으로 갈 수 있는 방법은 위에서 내려오는 방법 + 왼쪽에서 오른쪽으로 가는 방법이다.

따라서 dp[i][j] = dp[i-1][j] + dp[i][j-1]이라는 점화식을 통해 $O(n^2)$에 구할 수 있다.

조합

이 문제의 가장 큰 특징은 총 경로의 길이는 변하지 않는다. 반드시 위에서 아래로 20칸, 왼쪽에서 오른쪽으로 20칸을 가야한다.

그 외의 방법은 최단루트가 아니기 때문이다. 그렇기에 20, 20을 어떤 순서로 선택하는가 문제로 변형되는데 이는 조합으로 ${40}C{20}$임을 알 수 있다.

advanced idea

source code

long long 범위를 넘을 수도 있지만, 다음과 같은 방식으로 조합을 구했다.

안전하게 구하기 위해서는 DP를 추천한다.

#include <stdio.h>
#define ll long long

int main(){
    ll tot = 1;
    for(ll i = 40 ; i >= 21 ; i--){
        tot = (tot*i)/(41-i);
    }
    printf("%lld",tot);
}

Problem 015