[C++] BOJ_1932 정수 삼각형

문제: 백준 1932 (c++)

풀이과정

---

문제에 나온 삼각형을 조건에 맞게 보면 아래층은 위층의 대각선 왼쪽 또는 대각선 오른쪽 숫자를 선택할 수 있는데,

배열로 생각하여 정리해 보면, 현재가 i 층일 때 dp[i-1][j] 또는 dp[i-1][j-1]의 숫자를 선택할 수 있다는 것이다.

이 문제는 최댓값을 구하는 문제이기에 제일 위 쪽의 두 개의 층은 직접 dp를 더하여 최종 dp 배열의 값을 지정해 주고

그 이후부터는 최댓값을 최종 dp 배열에 넣어주면 되는데

---

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

그냥 이렇게 할 경우 양 끝의 배열들은 오직 dp[i - 1][j] 이 숫자나 dp[i - 1][j - 1] 이 숫자를 선택해야 하는

예외가 생기기에 if-else 문으로 예외 처리를 해주어야 한다.

#include <iostream>
#include <algorithm>
using namespace std ;

int main(){

    int n ;
    cin >> n ;

    int dp[501][501] ;
    int res = 0 ;

    for(int i = 0; i < n; i++){
        for(int j = 0; j <= i; j++){
            cin >> dp[i][j] ;
        }
    }

    dp[1][0] += dp[0][0] ; 
    dp[1][1] += dp[0][0] ;

    for(int i = 2; i < n; i++){
        for(int j = 0; j <= i; j++){

            if(j == 0) dp[i][j] += dp[i-1][j] ;
            else if(j == i) dp[i][j] += dp[i-1][j-1] ;
            else dp[i][j] += max(dp[i-1][j], dp[i-1][j-1]) ;
        }
    }

    for(int i = 0; i < n; i++){
        res = max(res, dp[n-1][i]) ;
    }
    cout << res ;
    
}