[C/C++] BOJ 1932 :: 정수 삼각형

BOJ 1932 :: 정수 삼각형

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

나의 풀이

1. 정수삼각형의 값을 2차원 배열에 저장한다.

2. 각 층마다 최댓값을 저장한다.

삼각형의 가장 왼쪽 값은 바로 윗층의 같은 열의 값 + 현재 값을 저장한다.

삼각형의 가장 오른쪽 값은 바로 윗층의 현재 열 - 1 의 값 + 현재 값을 저장한다.

나머지 값은 그 둘 중 최댓값 + 현재 값을 저장한다.

            if (j == 0) arr[i][j] += arr[i-1][j];

            else if (j == i) arr[i][j] += arr[i - 1][j - 1];

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

3. 마지막 층 중에서 최댓값을 구하여 출력한다.

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_1932/BOJ_1932.cpp

// 백준알고리즘 1932번 :: 정수삼각형
#include<iostream>
using namespace std;
#define max(a,b) (a > b) ? a : b
int n, ans;
int arr[502][502];
 
int main(void)
{
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            cin >> arr[i][j];
        }
    }
 
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            if (j == 0) arr[i][j] += arr[i-1][j];
            else if (j == i) arr[i][j] += arr[i - 1][j - 1];
            else arr[i][j] += max(arr[i - 1][j], arr[i - 1][j - 1]);
        }
    }
 
    ans = arr[n - 1][0];
    for (int i = 1; i < n; i++)
    {
        if (ans < arr[n - 1][i]) ans = arr[n - 1][i];
    }
 
    cout << ans;
 
    return 0;
}