2022.02.07 [백준] C# 정수 삼각형

 

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

1932번: 정수 삼각형

 

---

풀이

이 문제는 j = 0(왼쪽 끝)일 때와, 0 < j < i(중간에 위치할 때), j = i(오른쪽 끝)에 위치할 때 3가지 조건으로 생각하고 해결했습니다.

수가 삼각형의 변에 위치하면 자신의 위 값과 자신을 더해주고, 수가 중간에 위치하면 대각선 위의 수 중, 큰 수와 자신을 더해주면서 끝까지 내려 왔고, max함수를 이용해 그 중, 최대값을 구했습니다.

아래의 코드는 각 층의 수를 저장한 triangle함수의 배열 값에 바로 더하는 방식으로 풀었습니다.

using System;
using System.Text;
using System.IO;
 
class Program
{
    static int[,] triangle;
 
    static void Cal(int n)
    {
        
        for (int i = 1; i < n; i++)
        {
            for(int j = 0; j <= i; j++)
            {
                if (j == 0)
                {
                    triangle[i, j] = triangle[i - 1, j] + triangle[i, j];
                }
                else if (j == i)
                {
                    triangle[i, j] = triangle[i - 1, j-1] + triangle[i, j];
                }
                else
                {
                    triangle[i, j] = Math.Max(triangle[i - 1, j - 1], triangle[i - 1, j]) + triangle[i, j];
                }
                    
            }
        }
        
        
    }
 
    static int max(int n)
    {
        int max_score = 0;
        for(int i = 0; i < n; i++)
        {
            max_score = Math.Max(triangle[n-1, i], max_score);
        }
        return max_score;
    }
 
    static void Main()
    {
        StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
        StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));
        StringBuilder sb = new StringBuilder();
        int n = int.Parse(sr.ReadLine());
        triangle = new int[n, n];
        for (int i = 0; i < n; i++)
        {
            var num = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
            for(int j = 0; j < num.Length; j++)
            {
                triangle[i, j] = num[j];
            }
        }
        Cal(n);
        sw.WriteLine(max(n));
        sr.Close();
        sw.Close(); 
    } 
}

 

 

아래의 코드는 2차원배열인 sum을 만들어 각층에서 내려올 때의 합을 sum에 저장하는 방식으로 푼 코드입니다.

using System;
using System.Text;
using System.IO;
 
class Program
{
    static int[,] triangle;
    static int[,] sum;
 
    static void Cal(int n)
    {
        
        sum[0, 0] = triangle[0, 0];
        
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j <= i; j++)
            {
                if (j == 0)
                {
                    sum[i, j] = sum[i - 1, j] + triangle[i, j];
                }
                else if (j == i)
                {
                    sum[i, j] = sum[i - 1, j - 1] + triangle[i, j];
                }
                else
                {
                    sum[i, j] = Math.Max(sum[i - 1, j - 1], sum[i - 1, j]) + triangle[i, j];
                }
 
            }
        }
        
 
    }
 
    static int max(int n)
    {
        int max_score = 0;
        for (int i = 0; i < n; i++)
        {
            max_score = Math.Max(sum[n - 1, i], max_score);
        }
        return max_score;
    }
 
    static void Main()
    {
        StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
        StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));
        StringBuilder sb = new StringBuilder();
        int n = int.Parse(sr.ReadLine());
        triangle = new int[n, n];
        sum = new int[n, n];
        for (int i = 0; i < n; i++)
        {
            var num = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
            for (int j = 0; j < num.Length; j++)
            {
                triangle[i, j] = num[j];
            }
        }
        Cal(n);
        sw.WriteLine(max(n));
        sr.Close();
        sw.Close();
    }
}