[BOJ] 1932번: 정수 삼각형

1932번: 정수 삼각형

풀이

현재 칸을 기준으로 이전 칸에서 좌, 우를 비교해서 최댓값을 계속 축적해주면 된다. 그리고 마지막 줄을 순회하면서 최댓값을 구하는 방법.

코드

예전에 짠 코드

#include <cstdio>
const int MAX = 501;

int N, max = -1, i, j;
int v[MAX][MAX];

void input()
{
    scanf("%d", &N);
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= i; j++)
            scanf("%d", &v[i][j]);
}
int main()
{
    input();
    for (i = 2; i <= N; i++)
    {
        for (j = 1; j <= i; j++)
        {
            int l = v[i - 1][j];
            int r = v[i - 1][j - 1];
            if (l > r)
                v[i][j] += l;
            else
                v[i][j] += r;
            if (max < v[i][j])
                max = v[i][j];
        }
    }
    printf("%d\n", max);
    return 0;
}

방금 짠 코드 (vector 사용함)

#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;

int main()
{
    int n, Max = -1;
    scanf("%d", &n);

    vector<vector<int>> v;
    v.resize(n);
    for (int i = 0; i < n; ++i)
        for (int j = 0, a; j <= i; ++j)
        {
            scanf("%d", &a);
            v[i].push_back(a);
        }

    for (int i = 1; i < n; ++i)
        for (int j = 0; j <= i; ++j)
        {
            if (j == 0)
                v[i][j] += v[i - 1][j];
            else if (j == i)
                v[i][j] += v[i - 1][j - 1];
            else
                v[i][j] += max(v[i - 1][j], v[i - 1][j - 1]);
        }
    for (int i = 0; i < n; ++i)
        Max = max(Max, v[n - 1][i]);
    printf("%d\n", Max);
    return 0;
}