[백준] 1932 정수 삼각형 c++

 

문제 링크  https://www.acmicpc.net/problem/1932

KEY

• 프로그래머스 문제와 완전히 똑같은 문제이다. https://everydayyy.tistory.com/96
• 맨 왼쪽인 경우, 맨 오른쪽인 경우, 그렇지 않은 경우 총 3가지의 경우를 생각하여 더해나가면 된다.

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<string>
using namespace std;
int n;
int arr[501][501];
int dp[501][501];
int answer;
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            cin >> arr[i][j];
        }
    }
    //dp배열 초기화
    dp[0][0] = arr[0][0];
    dp[1][0] = arr[1][0];
    dp[1][1] = arr[1][1];
 
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0) { //맨 왼쪽의 경우
                dp[i][j] = dp[i - 1][j] + arr[i][j];
            }
            else if (j == n-1) { //맨 오른쪽의 경우
                dp[i][j] = dp[i - 1][j-1] + arr[i][j];
            }
            else { //나머지
                dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + arr[i][j];
            }
        }
    }
 
    for (int i = 0; i < n; i++) {
        answer = max(answer, dp[n - 1][i]);
    }
    cout << answer;
}