[Algorithm] Baekjoon 1932번 : 정수 삼각형

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

1932번: 정수 삼각형

int dp[501][501] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    int input = 0;
    int maxNum = 0;
 
    cin >> n;
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            cin >> input;
 
            int left = 0;
            int right = 0;
 
            if (j - 1 >= 0) left = dp[i-1][j - 1] + input;
            right = dp[i-1][j] + input;
 
            dp[i][j] = max(left, right);
 
            if (i == n)
            {
                maxNum = max(maxNum, dp[i][j]);
            }
        }
    }
 
    cout << maxNum;
}

 

삼각형 한줄씩 입력받기 때문에 바로 dp계산해서 값을 갱신한다.

i번째 층의 j번째값의 부모는 윗층(i-1)번째의 j-1과 j 이다.

다만, 맨 왼쪽인덱스(0) 같은 경우 j-1번째가 없기 때문에 적절히 조건을 걸어준다. ( if (j - 1 >= 0 )

input값에 각각의 부모값을 더했을 때 큰 값으로 갱신해주면 된다.

 

최종 최대값을 구해야하기 때문에 n번째에서의 최대값을 구하기위해 n번째 층에서는 maxNum값을 업데이트시켜주고 출력시켜주면 된다.