Problem 1.6.2 Number Triangles

출처: https://train.usaco.org/usacogate

---

문제 설명

Number Triangles
Consider the number triangle shown below. Write a program that calculates the highest sum of numbers that can be passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

          7

        3   8

      8   1   0

    2   7   4   4

  4   5   2   6   5
In the sample above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30.

입력

The first line contains R (1 <= R <= 1000), the number of rows. Each subsequent line contains the integers for that particular row of the triangle. All the supplied integers are non-negative and no larger than 100.

출력

A single line containing the largest sum using the traversal specified.

입력 예

5 
7 
3 8 
8 1 0 
2 7 4 4 
4 5 2 6 5

출력 예

30

---

문제 풀이 내용

읽어 들인 입력들을 2차원 배열에 저장한다. 첫번째 입력부터 아래로 내려가면서 더해간다. 양쪽에서 도착할 수 있는 경우, 2개위 상위 수에서 큰수를 기준으로 한다. 이렇게 마지막 행에 도착해서, 제일 큰 수를 출력한다. 

프로그램 내용

#define MAX_R 1001
#define MAX_N 100

int Tr[MAX_R][MAX_R] = {0};
int val[(MAX_R+1)*MAX_R/2] = {0};
int ret = 0;

int main() {
    /// Read 1 ~ idx number
    for (int i=0; i < R ; i++)
        for (int j=0; j<i+1 ; j++)
            fin >> Tr[i][j];

            idx1 = (i*(i+1)/2+j);
            if (i > 0)
                if(j == 0 )
                {
                    idx2 = idx3 = i*(i-1)/2;
                }
                else if (j == i)
                {
                    idx2 = idx3 = (i*(i-1)/2+j-1);
                }
                else
                {
                    idx2 = (i*(i-1)/2+j-1);
                    idx3 = (i*(i-1)/2+j);
                }

            }
            val[0] = Tr[0][0];
            val[1] = val[0] + Tr[1][0];
            val[2] = val[0] + Tr[1][1];

            if(idx1 > 2)
            {
                val[idx1] = max (val[idx2], val[idx3]) + Tr[i][j];
            }

            ret = max(ret, val[idx1]);

 

Chapter 1. Getting started