💛 오늘의 학습 키워드

[동적계획법] Pascal's Triangle

📝 문제

문제 설명

Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

제한 조건

• 1 <= numRows <= 30

입출력 예

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

Example 2

Input: numRows = 1
Output: [[1]]

💬 내 풀이

class Solution {
    public List<List<Integer>> generate(int numRows) {
        
        List<List<Integer>> result = new ArrayList<>();

        for(int i=0; i<numRows; i++) {
            List<Integer> list = new ArrayList<>();
            
            for(int j=0; j<=i; j++) {
                if(j == 0 || j == i) {
                    list.add(1);
                } else {
                    int prev = result.get(i-1).get(j-1);
                    int next = result.get(i-1).get(j);
                    list.add(prev+next);
                }
            }
            result.add(list);
        }
        return result;
    }
}

💻 내 접근 방법

1. 저장할 List<List<Integer>> 객체를 생성한 후, 이중 for문을 사용해서 문제를 풀었다.
2. 배열로 봤을 때 [i][0] 과 [i][j] (마지막 값) 은 항상 1의 값을 가지기 때문에 if문을 사용해서 값을 넣어준다.
3. 나머지는 이전 값을 차근차근 더해서 객체에 추가해준 후 리턴해준다.

💦 회고

처음에 int[][] 배열로 더한 후에 list<list> 로 변환하려고 했는데, 잘 안되었다. 내일 스터디 날에 질문 해야지.