problem 1.8

main.py

"""
# 문제 : 파스칼의 삼각형

* 파스칼의 삼각형은 수학의 이항 계수를 삼각형의 형태로 숫자를 배열한 구성을 말한다.

* 파스칼의 삼각형은 처음 두 줄을 제외하고 새로 만들어지는 줄의 새로운 숫자는  윗줄의 왼쪽 수와 오른쪽 수를 더해서 만들어진다.
* 또한 제일 맨 첫줄의 하나의 숫자는 1이다.

    1
  1   1

* 처음 두 줄은 위와 같이 구성할  수 있다.

    1
  1   1
1   2   1

* 다음 3번째 줄은 윗줄의 왼쪽 수와 오른쪽 수가 존재한다면 합하고, 그렇지 않다면 다음 줄의 수를 구성한다.
* 3번째 줄은 이전 단계에서 만들어진 숫자로 구성된다.
* 다만, 대각선 왼쪽과 오른쪽의 숫자가 있다면, 그 숫자의 합이 다음 단계의 숫자가 된다.

입력 : 파스칼의 삼각형을 구성할 줄의 수 예) 1, 2, 3
출력 : 파스칼의 삼각형을 구성하는 이차원 배열

## 제한 사항

- 입력값은 양의 정수이다.
- 반환 값은 2차원 배열이다. 예) n = 3 [[1], [1, 1], [1, 2, 1]]

## 아이디어

1. 기반 리스트를 생성한다.
2. 1번째 리스트 요소를 1로 초기화 한다.
3. 입력으로 주어진 행수만큼 순회한다.
  - 항상 행의 맨 앞과 맨 뒤의 값은 1이다.
  - 순회하면서 해당 줄(line)을 생성하기 위해서는 이전 행의 값을 참조하여 더하거나 그대로 사용한다.
  
시간 복잡도: O(n^2)
공간 복잡도: O(1)

## 구현
"""

from typing import List


def solve(numRows: int) -> List[List[int]]:
    pascal = []

    if numRows <= 0:
        return pascal

    pascal.append([1])

    for i in range(1, numRows):
        prev_len = len(pascal[i - 1])
        curr_list = []

        for j in range(prev_len + 1):
            num = 1
            if j != 0 and j != prev_len:
                num = pascal[i - 1][j - 1] + pascal[i - 1][j]
            curr_list.append(num)
        pascal.append(curr_list)
    return pascal


if __name__ == "__main__":
    print(solve(int(input())))

• 피라미드 형태의 배열의 인덱스를 알아보기 쉽게

1
1 1
1 2 1
1 3 3 1

• 이런식으로 표현하면, 인덱스 규칙을 파악하기가 좋을 것 같다.