[알고리즘 문제 풀기] 파스칼의 삼각형(16395)

1. 문제 풀이 아이디어

• 파스칼의 삼각형을 arr[i][j] = arr[i-1][j-1] + arr[i-1][j] 형태로 값을 채워 문제를 해결할 수 있다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    string[] split = sr.ReadLine().Split();
    int n = int.Parse(split[0]);
    int k = int.Parse(split[1]);

    int[][] arr = new int[n][];
    for (int i = 0; i < n; i++)
    {
        arr[i] = new int[i + 1];
        for (int j = 0; j < i + 1; j++)
        {
            if (j == 0 || j == i)
            {
                arr[i][j] = 1;
                continue;
            }
            arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
        }
    }
    sw.WriteLine(arr[n - 1][k - 1]);
}

3. 정리

• n과 k를 입력받아 int[][] arr 배열을 선언하고 파스칼의 삼각형을 생성한다.

• 첫 번째와 마지막 원소는 항상 1이므로 arr[i][0] = 1과 arr[i][i] = 1로 초기화한다.

• 나머지 값은 arr[i][j] = arr[i-1][j-1] + arr[i-1][j]를 이용하여 계산한다.

• 최종적으로 arr[n-1][k-1] 값을 출력하여 문제를 해결한다.