백준알고리즘 1932번 정수 삼각형 C#

세부 정보

• 사이트: 백준알고리즘
• 번호: 1932
• 문제명: 정수 삼각형
• 언어: C#
• 분류: 다이나믹 프로그래밍
• 비고: 

 

문제

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

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

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

 

입력

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

 

출력

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

 

풀이

StreamReader과 StreamWriter는 .NET에서 파일이나 스트림에 텍스트 데이터 작성에 사용하는 클래스다.

Console.OpenStandardInput()과 Console.OpenStandardOutput()은 콘솔의 표준 입출력을 사용한다는 의미다.

Array.ConvertAll()의 의미는 형식을 한번에 변환하며 () 안에 변환할 배열과, 변환할 형식을 지정할 수 있다.

StreamReader.Close()와 StreamWriter.Close()는 내부 스트림을 닫는다는 의미다.

// 텍스트 파일을 전문으로 출력하는 역할을 맡는다.
StreamWriter streamWriter = new StreamWriter(Console.OpenStandardOutput());
// 텍스트 파일을 전문을 입력하는 역할을 맡는다.
StreamReader streamReader = new StreamReader(Console.OpenStandardInput());

// 삼각형의 크기
int n = Convert.ToInt32(streamReader.ReadLine());

// 정수를 담을 삼각형을 2차원 배열 형태로 만든다
int[][] triangle = new int[n][];

// 삼각형의 맨 위에는 크기가 1인 배열이 들어간다.
triangle[0] = new int[1];
// 삼각형의 맨 위에 정수를 입력받아 넣는다.
triangle[0][0] = Convert.ToInt32(streamReader.ReadLine());

for (int i = 1; i < n; i++)
{
    // 입력받은 문자열을 공백으로 구분한 다음 전부 정수로 바꾸고 배열에 저장한다.
    int[] lines = Array.ConvertAll(streamReader.ReadLine().Split(), int.Parse);
    // 삼각형의 2번째 위부터 맨 밑까지의 배열의 길이를 넣는다.
    triangle[i] = new int[lines.Length];

    for(int j = 0; j < lines.Length; j++)
    {
        // 삼각형의 맨 왼쪽 값
        if (j == 0) triangle[i][j] = triangle[i - 1][j] + lines[j];
        // 삼각형의 맨 오른쪽에 있는 값
        else if (j == lines.Length - 1) triangle[i][j] = triangle[i - 1][j - 1] + lines[j];
        else // 두 개의 대각선 중 하나가 선택 가능한 정수
            triangle[i][j] = Math.Max(triangle[i - 1][j] + lines[j], triangle[i - 1][j - 1] + lines[j]);
    }
}

// 맨 밑에서 나온 최대값
int max = 0;

// 마지막 층에서 최대값 탐색
for (int i = 0; i < triangle[n - 1].Length; i++)
{
    if (max < triangle[n - 1][i])
        max = triangle[n - 1][i];
}

// 맨 밑에서 나온 최대값 출력
streamWriter.WriteLine(max);

// 개체와 내부 스트림을 닫고 출력 시스템 리소스 해제
streamWriter.Close();
// 개체와 내부 스트림을 닫고 입력 시스템 리소스 해제
streamReader.Close();

 

후기

이번 주는 다이나믹 프로그래밍 분류를 다루기로 했다. 문제를 선정했지만 난이도가 어떻게 되는 지 확인을 따로 하지 않아서 어려운 문제를 선택하고 말았다. 30분을 못 넘기고 제출해야 했지만 어려울수록 그만큼 얻어가는 것도 많을 것이다. 하지만 오늘 하루 안에 소화하는 것은 무리다. 이런 어려운 문제는 며칠을 걸쳐야 소화가 가능하다.