99클럽 코테 스터디 22일차 TIL Pascal's Triangle II

 

# 오늘의 학습 키워드 

동적 계획법

 

# 오늘의 문제 

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

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.

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

 

 

Example 1:

Input: rowIndex = 3

Output: [1,3,3,1]

Example 2:

Input: rowIndex = 0

Output: [1]

Example 3:

Input: rowIndex = 1

Output: [1,1]

 

Constraints:

• 0 <= rowIndex <= 33

 

# 나의 풀이방식 

class Solution {
    public List<Integer> getRow(int rowIndex) {

    // 두 수를 합치기 위해 2차원 리스트 선언
    List<List<Integer>> list = new ArrayList<>();

    for (int i = 0; i <= rowIndex; i++) {
        List<Integer> result = new ArrayList<>();

        // for문을 돌면서 이전 행의 값들을 더해준다
        for (int j = 0; j <= i; j++) {
            if(j==0 || j==i){
                result.add(1);
            }else {
                result.add(list.get(i-1).get(j-1) + list.get(i-1).get(j));
            }
        }

        list.add(result);
    }

    // 2차원 리스트의 마지막 행을 리턴
    return list.get(list.size()-1);
        
    }
}

 

# 다른사람 풀이

class Solution {
    public List<Integer> getRow(int rowIndex) {

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

        answer.add(1);

        if(rowIndex == 0){
            return answer;
        }

        long val = 1;

        for(int i = 1; i < rowIndex; i++){
            val = (val * (rowIndex - (i-1))) / i;
            answer.add((int)val);
        }

        answer.add(1);

  
    return answer;

 

# 오늘의 공부 

파스칼의 삼각형의 경우 이항정리를 이용해 이중for문 없이도 문제 풀이 가능!