피라미드 형태의 삼각형이 주어질때 아래로 내려가면서 최대의 값을 찾는 문제입니다

전략 : 별다른 전략 필요가 없네요

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <stdio.h>
#include <string.h>

using namespace std;

int dp[500][500];

int main(void) {
 memset(dp, -1, 0);
 int t;
 int max = -1;

#ifndef ONLINE_JUDGE
 freopen("input.txt", "r", stdin);
 freopen("output.txt", "w", stdout);
#endif

 scanf("%d", &t);
 for (int i = 0; i < t; i++) {
  for(int j=0;j<i+1;j++)
   scanf("%d", &dp[i][j]);
 }

 for (int i = 1; i < t; i++) {
  for (int j = 0; j < i + 1; j++) {
   if (j == 0) {
    dp[i][j] = dp[i][j] + dp[i-1][j];
   }
   else if (j == i) {
    dp[i][j] = dp[i][j] + dp[i-1][j-1];
   }
   else {
    dp[i][j] = dp[i][j] + (dp[i - 1][j] > dp[i - 1][j - 1] ? dp[i - 1][j] : dp[i - 1][j - 1]);
   }
  }
 }
 for (int i = 0; i < t; i++) {
  if (dp[t - 1][i] > max)
   max = dp[t - 1][i];
 }
 printf("%d\n", max);


 

#ifndef ONLINE_JUDGE
 fclose(stdin);
 fclose(stdout);
#endif

 return 0;
}