숫자삼각형 | 백준 1932번

#include <stdio.h>

int main(void) {
 // your code goes here
 
 int triangle[501][501];
 int sum[501][501]={0};
 int n, biggest=0;
 
 scanf("%d", &n);
 
 for(int i=1; i<=n; i++)
 {
  for(int j=1; j<=i; j++)
  {
   scanf("%d", &triangle[i][j]);
  }
 }
 
 sum[1][1] = triangle[1][1];
 for(int i=2; i<=n; i++)
 {
  for(int j=1; j<=i; j++)
  {
   int bigger = sum[i-1][j-1] > sum[i-1][j] ? sum[i-1][j-1] : sum[i-1][j];
   sum[i][j] = bigger + triangle[i][j];
  }
 }
 
    for(int i=1; i<=n; i++)
    {
       biggest = sum[n][i] > biggest ? sum[n][i] : biggest;
    }
    
 printf("%d\n", biggest);
 
 
 return 0;
}

와 같이 코드를 짰는데.. triangle[1][1]만 먼저 받으면, for문 두개를 하나로 합칠 수 있을 것 같다.
그러면 시간 효율은 2배정도 좋아지겠다만..

알고리즘 분류 : 다이나믹 프로그래밍

make better code

숫자삼각형 | 백준 1932번

Artikel Menarik Lainnya