SWEA 2005번: 파스칼의 삼각형 (D2) - Python 풀이

문제 설명

SW Expert Academy

크기가 N인 파스칼의 삼각형을 만들어야 한다.

파스칼의 삼각형이란 아래와 같은 규칙을 따른다.

1. 첫 번째 줄은 항상 숫자 1이다.
2. 두 번째 줄부터 각 숫자들은 자신의 왼쪽과 오른쪽 위의 숫자의 합으로 구성된다.

N이 4일 경우,

N을 입력 받아 크기 N인 파스칼의 삼각형을 출력하는 프로그램을 작성하시오.

[제약 사항]

파스칼의 삼각형의 크기 N은 1 이상 10 이하의 정수이다. (1 ≤ N ≤ 10)

[입력]

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.
각 테스트 케이스에는 N이 주어진다.

[출력]

각 줄은 '#t'로 시작하고, 다음 줄부터 파스칼의 삼각형을 출력한다.
삼각형 각 줄의 처음 숫자가 나오기 전까지의 빈 칸은 생략하고 숫자들 사이에는 한 칸의 빈칸을 출력한다.
(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

입력

1
4

input.txt

출력

#1
1
1 1
1 2 1
1 3 3 1

output.txt

풀이 과정

파스칼 삼각형의 각 행을 구할 때 이전의 행의 값을 사용한다는 것 + 계속 반복적인 작업을 하기 때문에 DP로 풀어야겠다고 생각했습니다.

1. DP 테이블 정의
   • DP[i] = 파스칼 삼각형의 i번째 줄
2. 점화식 도출
   • i = 4일 때,
     DP[4][0] = 1
     DP[4][1] = DP[3][0] + DP[3][1]
     DP[4][2] = DP[3][1] + DP[3][2]
     DP[4][3] = DP[3][2] + DP[3][3]
     DP[4][4] = 1
   • 이를 통해 1) j값은 1부터 i-1까지 돌고, 2) DP[i][j] = DP[i-1][j-1] + DP[i-1][j]가 된다는 것을 도출할 수 있습니다.
3. 초기값 설정
   • 일단 모든 행의 첫번째 열, 마지막 열은 1인 것이 자명하니 테이블 초기화 시 1로 초기화 하겠습니다.
   • DP[0] = 1, DP[1] = [1, 1]입니다. N이 2까지는 DP 테이블 그대로 출력하면 되고, N이 3부터는 2번의 점화식을 통해 값을 채워야 합니다.

정답 코드

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N = int(input())
    DP = [[1 for _ in range(i+1)] for i in range(N)]
 
    if N > 2:
        for i in range(2, N):
            for j in range(1, i):
                DP[i][j] = DP[i-1][j-1] + DP[i-1][j]
 
    print("#%d" % test_case)
    for i in range(N):
        print(* DP[i])

이상입니다.