[백준 / BOJ] C++ 1932 정수 삼각형

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

풀이

문제에서 주어지는 조건을 활용해보자.

아래층으로 내려올때 선택 할 수 있는 수는 윗층에서의 대각선에 위치한 수이다. 

즉, 위의 이미지를 참조하여 써보겠다.

• node[0][0] = 7
• node[1][0] = 해당 node + node[0][0], node[1][1] = 해당 node + node[0][0]
• node[2][0] = 해당 node + node[1][0], node[2][1] = 해당 node + max(node[1][0], node[1][1]), ...

왼쪽 끝노드와, 오른쪽 끝 노드는 항상 해당 node + 바로 위 node를 더한 값이다.

그리고 중간지역의 노드들은 해당 node + 해당 node의 왼쪽 위, 오른쪽 위 노드들의 큰 수를 더한 값이다.

 

이 조건을 이용하면 비교적 간단하게 풀 수 있다.

 

아래 코드를 참조하자

 

Code ( C++ )

#include <iostream>
#include <algorithm>

using namespace std;

int node[501][501];
int N;
int result;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < i + 1; j++)
        {
            int node_value;
            cin >> node_value;
            node[i][j] = node_value;
        }
    }

    result = 0;

    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < i + 1; j++)
        {
            if(j == 0)
                node[i][j] = node[i - 1][j] + node[i][j];
            else if(i == j)
                node[i][j] = node[i - 1][j - 1] + node[i][j];
            else
                node[i][j] = max(node[i - 1][j - 1] + node[i][j], node[i - 1][j] + node[i][j]);    

            result = max(result, node[i][j]);
        }
    }
    cout << result << "\n";
}