LeetCode 118 - Pascal's triangle ( C++ )

 

처음으로 한방에 풀어버린 dp 문제네요

---

문제 풀이

 

numRows의 범위가 1 이상 30 이하이므로 파스칼의 삼각형을 미리 만들어버리고 numRows값에 따라 알맞은 vector<vector<int> 배열을 생성하여 반환합니다.

 

파스칼의 삼각형을 어떻게 만드느냐가 포인트죠.

 

1. 우선 31,31 2차원 배열 mat을 만듭니다.

 

2. 파스칼 삼각형의 맨 꼭대기와 바로 아래 줄은 다 1이므로 mat[0][0] , mat[1][0], mat [1][1]에 다 1을 저장합니다

 

3. 2차원 배열의 2행부터 30행까지 선형반복문을 통해서 알맞은 값을 저장해 나가면 됩니다. 

 

파스칼 삼각형의 각 줄에서 맨 왼쪽값과 맨 오른쪽 값은 1이고 그 외의 값은 (이전행, 같은열)값 + (이전행, 같은열-1)값을 저장합니다.

 

 

파스칼 삼각형을 다 만들었으면 numRows값에 따라 알맞은 vector<vector<int> 타입의 2차원 배열을 만들어 반환합니다.

 

---

코드

 

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        
        vector<vector<int>> ans;
        
        int mat[31][31] = {0,};
        mat[0][0] = 1;
        mat[1][0] = 1;
        mat[1][1] = 1;
        
        for (int i = 2 ; i <= 30 ; i++ ) {
            for (int j = 0 ; j <= i ; j++) {
                
                if ( j == 0 ) {     // 파스칼 삼각형 각 행의 맨 오른쪽 값
                    mat[i][j] = 1;
                }
                else if ( j == i ) {    // 파스칼 삼각형 각 행의 맨 왼쪽 값
                    mat[i][j] = 1;
                }
                else    // 그 외
                    mat[i][j] = mat[i-1][j] + mat[i-1][j-1];
            }
        }
        
        for (int i = 0 ; i < numRows ; i++) {   // 알맞은 vector<vector<int>> 2차원 배열 생성
            vector<int> v(i+1);
            
            for (int j = 0; j <= i ; j++) 
                v[j] = mat[i][j]; 
            
            ans.push_back(v);
        }
        
        return ans;
    }
};

 

---

결과

 

 

 

메모리 사용량은 좀 밀리네요