[백준 1932] 정수 삼각형

0. 제목

• 백준 1932 정수 삼각형
• BOJ 1932 정수 삼각형
• C++ 1932 정수 삼각형

---

1. 문제

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

---

2. 풀이

• 합이 최대가 되는 경로에 있는 수의 합을 출력하는 것이 문제이다.
• 2차원 배열 arr, dp를 할당하고 arr는 각 위치의 값이 담기고 dp는 그 위치로 갔을 때의 합이 담긴다.
• 그런데 합이 최대가 되어야 하므로 전 단계에서 즉, 윗 줄에서 왼쪽과 오른쪽중 큰 것을 선택해야 한다.
• 따라서 점화식은 다음과 같다.
• dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j]
• 그런데 좌표를 arr[1][1] 부터 시작하도록 설정하였으며 i-1 이 0이 나오는 dp[i][0]들은 0으로 초기화 시켜놓았기 때문에 계산상 문제가 없다.
• 결론적으로 주어진 n번째 줄에서의 최대 합을 찾아야 하므로 최댓값을 구하는 알고리즘을 사용하면 된다.

---

3. 코드

#include <iostream>
#include <algorithm>
using namespace std;
 
int arr[501][501];
int dp[501][501] = {0};
 
int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            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] = max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j];
        }
    }
    int max = 0;
    for(int i = 1; i <= n; i++){
        if(max < dp[n][i])
            max = dp[n][i];
    }
    
    cout << max << '\n';
    
    return 0;
}