[0621] 알고리즘

1932. 정수 삼각형

  다이내믹 프로그래밍 문제. 원래는 재귀를 이용하여 해결하려 했지만 생각해보니 굳이 재귀 안 써도 반복문으로 풀 수 있겠다 싶어서 노선을 바꾸었다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

int triangle[501][501];
int memory[501][501];

int main()
{
    std::cin.tie(NULL);
    std::ios_base::sync_with_stdio(false);

    int n, max = 0;    

    std::cin >> n;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            std::cin >> triangle[i][j];
        }
    }

    memory[0][0] = triangle[0][0];

    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            if (j == 0)
            {
                memory[i][j] = memory[i - 1][j] + triangle[i][j];
            }
            else if (j == i)
            {
                memory[i][j] = memory[i - 1][j - 1] + triangle[i][j];
            }
            else
            {
                memory[i][j] = (memory[i - 1][j - 1] > memory[i - 1][j] ? memory[i - 1][j - 1] : memory[i - 1][j]) + triangle[i][j];
            }
        }
    }

    for (int i = 0; i < n; i++)
    {
        if (max < memory[n - 1][i]) max = memory[n - 1][i];
    }

    std::cout << max << '\n';

    return 0;
}

 

  memory 배열은 삼각형 속 각 숫자까지 도달할 때 나올 수 있는 각 경로 속 숫자들의 합의 최대값을 저장한다. 이 배열을 이용해 (i, j)의 최대값은 그 위에 있는 두 수((i-1, j-1)랑 (i-1, j)) 중 더 큰 값에 자신의 값을 더하여 구하는 식으로 진행.

 

  조금 더 생각해보면 재귀로도 풀 수 있지 않을까?