1932.정수 삼각형

이번에 풀어볼 문제는 백준 1932번 정수 삼각형이다.

1932번: 정수 삼각형

정말 쉬워보이지만 자신의 인접한 대각선의 숫자로만 합을 구해야한다는 점을 해결해야만

이 문제를 풀 수 있다. 이 문제를 푸는 방법은 대표적으로 DP 동적계획법을 사용하는 것이다.

 

 

---

 

 

* 제일 꼭대기의 값 부터 값을 누적해서 진행하되 겹치는 부분은 둘 중 큰 값으로 누적하면 된다 *

 

 

 

---

 

 

< Code 설명 >

#pragma warning(disable:4996)
#include <iostream>
#include <algorithm>
 
#define MAX 501
 
using namespace std;
 
int map[MAX][MAX];
 
int N;
 
int main(){
    freopen("1932.txt", "r", stdin);
    cin >> N;
 
    for (int i = 0; i < N; i++){   
        for (int j = 0; j <= i; j++){
            cin >> map[i][j];
        }
    }
    
    for (int i = 1; i < N; i++){
        for(int j = 0; j <= i; j++){
            if (j==0) // 가장 왼쪽의 대각선에 존재하는 경우 위의 가장 왼쪽 대각선의 값을 누적해서 가져오면 된다.
                map[i][j] += map[i-1][j];
            else      // 하지만 가장 왼쪽의 대각선을 제외한 나머지 위치의 경우 오른쪽 대각선과 왼쪽 대각선 중에 골라야하며
                map[i][j] += max(map[i - 1][j - 1], map[i - 1][j]); // 이럴 경우 그중 큰 수를 가져오면 된다.
         // 가장 오른쪽에 위치한 값의 경우도 이렇게 진행하면 존재하지 않는 값(0)과 가장 오른쪽대각선 중 큰 값을 비교할 것이기 때문에 가능하다.
        }
    }
    int ans = 0;
 
    for (int i = 0; i < N; i++)
        ans = max(ans, map[N-1][i]);
 
    cout << ans << endl;
    return 0;
}