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

三年になり、計算量や情報理論、プログラミングの使用など、面白い授業ばっかりで、友達ともあえて充実した大学生活を送れています！
どうも、マツケンです！

遅れましたが、書きます！

<考え方>
・下から一段ずつ比較していって、その都度二次元配列にその和の値を入れていく形。
・最初は14行目にある数値に対して隣接する15行目の数字の和のうち、大きいほうを二次元配列MAX_triangleに入れていく。
・次回以降、k+1行目のtriangleにある数値に対して、隣接するk行目のMAX_triangleの和のうち大きいほうを...という感じに頂点の数まで繰り返す。
・MAX_triangleの頂点の数値が求める数になる。<ソースコード>

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

int main(void){
    clock_t start_clock, end_clock;
    int triangle[15][15]={
        {75, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {95,64, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {17,47,82, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {18,35,87,10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {20,04,82,47,65, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {19,01,23,75,03,34, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {88,02,77,73,07,63,67, 0, 0, 0, 0, 0, 0, 0, 0},
        {99,65,04,28,06,16,70,92, 0, 0, 0, 0, 0, 0, 0},
        {41,41,26,56,83,40,80,70,33, 0, 0, 0, 0, 0, 0},
        {41,48,72,33,47,32,37,16,94,29, 0, 0, 0, 0, 0},
        {53,71,44,65,25,43,91,52,97,51,14, 0, 0, 0, 0},
        {70,11,32,28,77,73,17,78,39,68,17,57, 0, 0, 0},
        {91,71,52,38,17,14,91,43,58,50,27,29,48, 0, 0},
        {63,66,04,68,89,53,67,30,73,16,69,87,40,31, 0},
        {04,62,98,27,23, 9,70,98,73,93,38,53,60,04,23}};
    int MAX_triangle[14][14]={
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0}};
    int i,a,b,j;

start_clock = clock();
for(i=0; i<14; i++){
    a=triangle[13][i]+triangle[14][i];
    b=triangle[13][i]+triangle[14][i+1];
    if(a<b) MAX_triangle[13][i]=b;
    if(a>b) MAX_triangle[13][i]=a;
}

for(i=1; i<14; i++){
    for(j=0; j<14-i; j++){
        a=triangle[13-i][j]+MAX_triangle[14-i][j];
        b=triangle[13-i][j]+MAX_triangle[14-i][j+1];
        if(a>b) MAX_triangle[13-i][j]=a;
        if(b>a) MAX_triangle[13-i][j]=b;
    }
}
      printf("最大値%d\n", MAX_triangle[0][0]);
end_clock = clock();
printf("経過時間%f秒\n", (double)(end_clock - start_clock) / CLOCKS_PER_SEC);

return 0;
}

//クリアー

<実行結果>

最大値1074
経過時間0.000000秒

なんか、「2か月前の自分は何でこんなプログラム書いたんだろう...」って思いました。もっとコンパクトにまとめたい！

マツケンのマインド

とある理系大学生のブログです。基本は勉強とつぶやきとまとめです。

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