본문 바로가기
TIL

파스칼의 삼각형

by 도쿠니 2022. 4. 1.

 

 
파스칼의 삼각형은 다음과 같이 만들 수 있다.

1. 첫 번째 줄에는 숫자 1을 쓴다.
2. 그 다음 줄은 바로 위의 왼쪽 숫자와 오른쪽 숫자를 더한다.
 
입력 출력
1 [[1]]
3 [[1], [1, 1], [1, 2, 1]]
5 [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

처음으로 완벽하게 풀어서 올려봅니다.. 흑흑

import java.util.ArrayList;

public class Practice1 {
    public static ArrayList<ArrayList<Integer>> solution(int numRows) {
        ArrayList<ArrayList<Integer>> outer = new ArrayList<>(); // 파스칼 삼각형 전체

        for (int i = 0; i < numRows; i++) { // 들어오는 수가 곧 행의 수, 행의 수만큼 반복
            ArrayList<Integer> inner = new ArrayList<>(); // 각 행을 의미

            for (int j = 0; j <= i; j++) {  // 행 안에 들어가는 요소의 전체 개수 = 행의 번호, 첫번째줄엔 값이 하나, 두번째줄엔 값이 두개...
                if (j == 0 || j == i) { // 파스칼 삼각형은 처음과 마지막은 무조건 1이 들어감
                    inner.add(1);
                } else { // 그 외에는 이전 행에서 현재 인데스 -1 인덱스 + 현재 인덱스 값을 가져와서 더해준다.
                    ArrayList<Integer> prior = outer.get(i - 1);
                    inner.add(prior.get(j - 1) + prior.get(j));
                }
            }
            outer.add(inner); 
        }

        return outer;
    }

    public static void main(String[] args) {
        // Test code
        System.out.println(solution(1));
        System.out.println(solution(2));
        System.out.println(solution(3));
        System.out.println(solution(4));
        System.out.println(solution(5));
    }
}

반복문에서 i 는 행을, j는 열(=리스트에 들어갈 값들)을 의미한다고 생각하고 풀었다.

생각보다 쉬웠던 듯! 빠르게 규칙을 찾아내서 밑그림을 그리고 그 다음 코드로 옮기니까 금방 풀었다.

댓글