백준 1932 정수 삼각형 / C++

문제 : 1932

풀이 point

왼쪽에서 오는 값과 오른쪽에서 오는 값 중 최대를 골라 가장 최대를 구하면 된다.
테이블레이션 기법으로 dp[i][j]일 때 I는 층을 j는 I층 중 j번째 값을 의미한다.

풀이 방법

왼쪽에서 오는 값과 오른쪽에서 오는 값 중 최대를 계속해서 취하면 된다. (가장 최대의 경로로만 왔을 것이기 때문)

왼쪽은 dp[i-1][j-1] 오른쪽은 dp[i-1][j]이다. 예제로 입력되는 삼각형 모양을 보면 오른쪽 대각선 값은 왼쪽과 다르게 바로 위임을 알 수 있다.

코드

//백준 1932, 정수 삼각형

#include <iostream>

int arr[505][505];
int dp[505][505];

int main (){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    
    int N;
    std::cin >> N;

    for(int i{1}; i<=N; ++i){
        for(int j{1}; j<=i; ++j){
            std::cin >> 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] = std::max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j];
        }
    }
    
    int max{0};
    for(int i{1}; i<=N; ++i){
        max = std::max(dp[N][i], max);
    }
    
    std::cout << max;

    return 0;
}

2025-02-20T08:27:15.148Z