[코테연습] 118. Pascal's Triangle

 

https://leetcode.com/problems/pascals-triangle/description/

 

이 문제는 numRows 를 1 .. 부터 numRows 까지 증가하면서 증가값에 대한 배열을 반환하는 문제였다. 전형적인 dp 를 사용해야 푸는 것이 빠른 문제이다.

 

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

 

 

문제를 푼 방법은 다음과 같다

 

1. 배열만들기 [1], [2], [3], [4], [5]

        List<List<Integer>> result = new ArrayList<>();

        for (int i = 1; i <= numRows; i++) {

            List<Integer> list = new ArrayList<>();

            for (int j = 0; j < i; j++) {

                list.add(1);

            }

            System.out.println(list);

            result.add(list);

        }

2. dp 만들기

dp[0] = 1

dp[0] = 1, dp[1] = 1,

(1) n = 3

> dp[1] = dp[1] + dp[0];

dp[0] = 1, dp[1] = 2, dp[2] = 1

(2,1) n = 4 : n-2 부터 1까지

> dp[2] = dp[2] + dp[1] = 3

> dp[1] = dp[1] + dp[0] = 3

dp[0] = 1, dp[1] = 3, dp[2] = 3, dp[3] = 1,

( 3, 2, 1 ) n = 5 : n-2 부터 1까지

> dp[3] = dp[3] + dp[2] = 4

> dp[2] = dp[2] + dp[1] = 6

> dp[1] = dp[1] + dp[0] = 4

 

먼저 위와 같이 output 에 2차원 배열이 출력될 수 있도록 배열 값을 만들었다. 그 이후 dp 를 사용하여 규칙을 세웠다.

 

length가 n-2 값부터 1이 될때까지 반복하면서 

dp[j] = dp[j] + dp[j-1] 가 성립되어야한다. 이때 역순으로 해야 이전 dp[j] 값을 덮어쓰지 않으므로 역순으로 반복하였다.

 

답은 다음과 같다.

 

 

class Solution {
    public List<List<Integer>> generate(int numRows) {
        int[] dp = new int[numRows];
        Arrays.fill(dp, 1);

        List<List<Integer>> result = new ArrayList<>();
        for (int i = 1; i <= numRows; i++) {
            List<Integer> list = new ArrayList<>();
            
            for (int j = i-2; j >= 1; j--) {
                dp[j] = dp[j] + dp[j-1];
            }
            for (int j = 0; j < i; j++) {
                list.add(dp[j]);
            }
            result.add(list);
        }

        return result;        
    }
}