[알고리즘 문제 풀기] 정수 삼각형(1932)

1. 문제 풀이 아이디어

• 다이나믹 프로그래밍(DP)를 사용해 삼각형의 각 위치에서 선택 가능한 최대 경로 값을 누적하여 마지막 행에서 최댓값을 구해 문제를 해결한다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int n = int.Parse(sr.ReadLine());
    int[][] a = new int[n][];
    for (int i = 0; i < n; i++)
    {
        a[i] = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
    }
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < i + 1; j++)
        {
            int l = j > 0 ? a[i - 1][j - 1] : 0;
            int r = j < i ? a[i - 1][j] : 0;
            a[i][j] += Math.Max(l, r);
        }
    }
    int max = 0;
    for (int i = 0; i < n; i++)
    {
        max = Math.Max(max, a[n - 1][i]);
    }
    sw.WriteLine(max);
}

3. 정리

• for (int i = 1; i < n; i++) 루프로 두 번째 행부터 누적 최대 합을 계산한다.

• l = j > 0 ? a[i - 1][j - 1] : 0 → 왼쪽 위에서 내려오는 값

• r = j < i ? a[i - 1][j] : 0 → 바로 위에서 내려오는 값

• a[i][j] += Math.Max(l, r)를 통해 두 값 중 큰 값을 현재 위치에 누적한다.

• for (int i = 0; i < n; i++) 루프를 통해 마지막 행의 최댓값을 계산한다.

• max = Math.Max(max, a[n - 1][i])를 반복하여 최댓값을 갱신한다.

• 최종적으로 max값을 출력하여 문제를 해결한다.