[Leetcode] 118. Pascal's Triangle

Identifying the Problem

row 층 까지 파스칼 삼각형을 만들어 리턴한다.

파스칼 삼각형

Organizing thoughts

파스칼 삼각형의 규칙은 간단하다.

• 양 끝은 항상 1로 끝나고
• 그 사이의 값들은 이전 층의 0번째 + 1번째 ... n-1번째 + n번째의 합으로 이뤄진다.
  단 이 규칙은 row가 3 이상일 때부터 적용된다.

Sourcecode

int** generate(int numRows, int* returnSize, int** returnColumnSizes){

    int** arr; //정답 어레이를 선언
    arr = (int**) malloc ( sizeof(int*) * numRows ); //행 배열 동적할당
    
    for(int i=0; i<numRows; i++)
    {
        arr[i] = (int*) malloc ( sizeof(int) * (i+1) ); //열 동적할당
        arr[i][0] = 1; //양 끝은 1
        arr[i][i] = 1;
    }   
    
    *returnSize = numRows;   //13 ~ 18줄은 test assert용
    *returnColumnSizes = (int*) malloc (sizeof(int) * numRows);
    
    
    for(int i = 0; i<numRows; i++)
        (*returnColumnSizes)[i] = i+1;
    
    int k=2; //row가 3 이상일때부터
    
    while(numRows>2 && k<numRows)
    {
         for(int i=1;i<k ;i++)
            arr[k][i] = arr[k-1][i-1] + arr[k-1][i]; 
            //이전층의 이전 index 와 현재 index를 합한다.
    

         k++; //다음 층으로 이동
    }



    
 return arr;
}