[백준 - C#] 1932번 정수 삼각형

문제링크

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

문제

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

조건

시간제한 : 2초
메모리 제한 : 128 MB

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

 

문제정리

1. 첫째 줄부터 N번째 줄까지 선택된 수의 합이 최대가 되는 경로를 구해야합니다.
2. 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택 가능 합니다.

이번 문제의 경우 맨 위에 줄부터 맨 아래줄까지 내려오며 나온 값들 중 최대 값을 구하는 문제입니다.

해당 문제도 dp를 이용하여 풀이 하였으며 트리 구조로 내려올 때 모든 경로의 경우의 수를 다 찾아서 풀이를 진행하였습니다.

 

첫번 째 줄을 제외한 두번 째 줄부터 맨 왼쪽값과 맨오른 쪽 값을 제외한 나머지는 왼쪽 오른쪽 대각선 중 큰 수를 선택 하여야 합니다.

 

예제 문제를 보면 맨 왼쪽의 경우 7+3+8+2+4 순서로 가기 때문에 dp[i][j] = dp[i-1][j] + input값이고,

맨 오른쪽의 경우 7+8+0+4+5로 가기 때문에 dp[i][j] = dp[i-1][j-1] + input 값입니다.

위에서 i의 값은 N번째 줄이며 j의 값은 해당하는 줄의 정수 갯수입니다.

 

두개의 대각선을 선택할 수 있는 점화식의 경우에는

dp[i][j] = Max (  dp[i-1][j] + input, dp[i-1][j-1] + input ) 으로 대각선 왼쪽 값과 오른쪽 값 중 큰수를 찾아 주면 됩니다.

 

그리고 마지막으로 모든 dp 값이 계산이 되면 N번째 줄에 max 값을 찾아내면 문제를 풀 수 있습니다.

 

C# 코드

static void Main(string[] args)
{
    StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
    StreamReader reader = new StreamReader(Console.OpenStandardInput());
 
    int N = int.Parse(reader.ReadLine());
 
    int[][] dp = new int[N][];
 
    dp[0] = new int[1];
    dp[0][0] = int.Parse(reader.ReadLine());
 
    for (int i = 1; i < N; i++)
    {
        int[] input = Array.ConvertAll(reader.ReadLine().Split(), int.Parse);
 
        dp[i] = new int[input.Length];
 
        for (int j = 0; j < input.Length; j++)
        {
            if (j == 0) // 맨 왼쪽에 있는 값의 점화식
                dp[i][j] = dp[i - 1][j] + input[j];
            else if (j == input.Length - 1) // 맨 오른쪽에 있는 값의 점화식
                dp[i][j] = dp[i - 1][j - 1] + input[j];
            else // 두개의 대각선을 선택할 수 있는 정수의 점화식
                dp[i][j] = Math.Max(dp[i - 1][j] + input[j], dp[i - 1][j - 1] + input[j]);
        }
    }
 
    int max = 0;
    // 마지막 층에서 최대값을 찾는 반복문
    for (int i = 0; i < dp[N - 1].Length; i++)
    {
        if (max < dp[N - 1][i])
            max = dp[N - 1][i];
    }
 
    writer.WriteLine(max);
 
    writer.Close();
    reader.Close();
}

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.