[Algorithm] 파스칼의 삼각형 알고리즘 구현하기 (Pascal's triangle) - Java

파스칼 삼각형

파스칼의 삼각형은 블레즈 파스칼에 의해 제안된 삼각형으로 구성된 배열이다.

파스칼의 삼각형은 다음과 같은 규칙이 있다.

• 각 행의 첫 번째와 마지막의 숫자는 1이다.
• 각 행의 중간에 위치한 숫자는 이전 행의 왼쪽 위치에 있는 숫자와 바로 위에 있는 숫자의 합이다.

 

구현

위 두 규칙을 통해 파스칼의 삼각형을 2차원 배열로 구현해 보자.

public class Main {
    public static void main(String[] args) {
        int n = 7;

        // 파스칼의 삼각형 만들기
        int[][] pascal = new int[n][];
        for (int i = 0; i < n; i++) {
            pascal[i] = new int[i + 1];

            // 규칙 1. 각 행의 첫 번쨰와 마지막 숫자는 1
            pascal[i][0] = 1;
            pascal[i][i] = 1;

            // 규칙 2. 중간에 위치한 숫자는 이전 행의 왼쪽에 있는 숫자와 바로 위에 있는 숫자의 합
            for (int j = 1; j < i; j++) {
                pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j];
            }
        }

        // 파스칼의 삼각형 출력
        for (int i = 0; i < pascal.length; i++) {
            for (int j = 0; j < pascal[i].length; j++) {
                System.out.print(pascal[i][j] + " ");
            }
            System.out.println();
        }
    }
}

// 출력
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 
1 6 15 20 15 6 1