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

#include <iostream>

using namespace std;

int main(void){
    int n, maxNum = 0;
    int arr[501][501]; // 값 입력 받는 arr 0 ~ 500
    int dp[501][501] = {0}; // 합계 구할 arr 0 ~ 500
    scanf("%d", &n);

    for(int i = 1; i <= n; i++){ // 1부터 하는 이유는 인덱스 벗어나지 않게 하려고
        for(int j = 1; j <= i; j++) {
            scanf("%d", &arr[i][j]); //값 입력받기
        }
    }

    dp[1][1] = arr[1][1]; // 첫째 줄 값
    for(int i = 2; i <= n; i++){ // 삼각형 두번째 줄 부터 값 합산 시작
        for(int j = 1; j <= i; j++){ 
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j]; // 해당 인덱스와 그 전 줄에서 큰 것 합산
        }
    }

    for(int i=0; i<=n; i++){
        if(maxNum < dp[n][i]){ // 마지막 줄이 결과 값
            maxNum = dp[n][i];
        }
    }

    printf("%d", maxNum);

    return 0;
}

오늘의 키포인트

• 파스칼의 삼각형을 이용한 문제.
  백준 1010 다리놓기 문제와 굉장히 비슷하다.

• 0부터 배열을 시작하면 0 - 1 이 인덱스의 범위를 벗어나기에 1부터 인덱스를 사용하도록 하였다.

• 위에서 아래로가 아니라 아래서 위로 생각하자. 합산값은 윗줄의 최대값과 자신의 값을 더한 것과 같다.

• 점화식

dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j];