118. Pascal's Triangle

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

Pascal's Triangle - LeetCode

 

정수가 주어졌을 때 그에 해당하는 파스칼 삼각형을 만들어야 하는 문제다.

내려갈수록 이전 줄에서 원소의 덧셈을 아랫줄의 원소로 만드는 내용인데 대략 아래와 같은 구조이다.

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

2는 윗 줄 2개의 1+1로, 3은 윗 줄 1+2, 2+1로, 4는 윗 줄 1+3, 3+1, 6은 윗 줄 3+3의 결과로 나오는 식이다.

 

<C++>

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ret(numRows);
        
        for (int i = 0; i < numRows; ++i)
        {
            ret[i].resize(i + 1);
            ret[i][0] = ret[i][i] = 1;
            
            for (int j = 1; j < i; ++j) {
                ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
            }
        }
        
        return ret;
    }
};

 

<Python3>

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        if numRows == 0: return ret
        
        ret = [[1]]
        if numRows == 1: return ret

        for i in range(1, numRows):            
            row = [1]
            for j in range(1, i):
                row.append(ret[i - 1][j - 1] + ret[i - 1][j])
            row.append(1)
            ret.append(row)            
        return ret