プロジェクトオイラー 問題１５

こんにちは、マツケンです。

今回の問題↓
Problem 15 - PukiWiki

<考え方>
・高校数学で習う「最短経路問題」の考え方。
・数値が大きくなりすぎないように工夫して計算。(配列を使うと時間計算量大きくなるため)
・ほかにはないかな...<ソースコード>

/*
    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.


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

#include <stdio.h>
#include <time.h>

int main(void){
    long long ans = 1;
    clock_t start, end;

    start = clock();

    for(int i = 1; i <= 40; i++){
        ans *= i;
        if(i <= 20)
        ans /= i;
        else{
            ans /= (i - 20);
        }
    }

    end = clock();

    printf("Ans = %lld\n", ans);
    printf("経過時間%d[ms]\n", end - start);

    return 0;
}

<実行結果>

Ans = 137846528820
経過時間0[ms]

ここら辺はすいすいですね！