[SWEA] 2005. 파스칼의 삼각형

[SWEA] 2005. 파스칼의 삼각형

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

파스칼의 삼각형은 아래의 규칙이 있습니다.

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

N이 4일경우에는

1

1 1

1 2 1

1 3 3 1

이러한 모양을 띕니다.

우선 보고나서 바로 행렬이 생각이 났습니다.

	1	2	3	4
1	1
2	1	1
3	1	2	1
4	1	3	3	1

그리고 찾은 특징이 삼각형의 양쪽 빗면이 숫자 1이고 안이 같은 숫자로 구성되어 있다는 것을 찾았습니다.

그래서 작성한 풀이는 아래와 같습니다.

T = int(input())
for i in range(1, T+1):
    N = int(input())
    print(f'#{i}')
    for a in range(1, N+1):
        new = ''
        for b in range(1, N+1):
            if b <= a:
                if a == b:
                    new += "1 "
                elif b == 1:
                    new += "1 "
                else:
                    new += str(a - 1) + " "

        print(new)

테스트는 통과했으나 이렇게 하면 큰 오류가 생깁니다.

파스칼의 삼각형은 자신의 왼쪽과 오른쪽 위라는 표현이 잘못된 해석을 낳을 수 있습니다.

파스칼의 삼각형은 자신의 위에 위치하는 행에서 왼쪽과 오른쪽의 합입니니다.

위에 작성한 표 기준 (4, 3)은 (3, 2)와 (3, 3)의 합입니다.

실제 삼각형의 그림에서도 위 두 수의 합이 아래에 행에 두 수의 사이에 위치하는 값과 같습니다.

출처

그렇다면 다시 생각해야 합니다.

T = int(input())
for i in range(1, T+1):
    N = [k for k in range(1, int(input())+1)]
    print(f'#{i}')
    new = []
    new2 = []
    for i in N:
        new2 += new
        new.clear()
        for j in N:
            if j <= i:
                if i == j or j == 1:
                    new.append(1)
                else:
                    new.append(new2[j-2] + new2[j-1])
        new2.clear()
        print(' '.join(list(map(str, new))))

N x N크기의 행렬을 생성하고 열 크기가 행보다 작게 설정해 줍니다. 그리고 열이 1이거나 행과 열의 값이 같을 때 1을 출력합니다.

나머지를 구하기 위해서 리스트를 생성해주는데 이전 행의 값을 저장할 리스트와 현재 행의 값을 저장할 리스트를 생성합니다. 그리고 저장한 리스트 값을 빈 리스트에 더해주고 현재 값을 가지고 있는 리스트는 리셋합니다.

작성하면서 clear를 쓰지 않아도 가능 할 것 같아서 다시 작성했습니다.

T = int(input())
for q in range(1, 1 + T):
    N = [k for k in range(int(input()))]
    print(f'#{q}')
    for i in N:
        now = []
        for j in N:
            if j <= i:
                if i == j or j == 0:
                    now.append(1)
                else:
                    now.append(save[j-1] + save[j])
        save = []
        save += now
        print(' '.join(list(map(str, now))))

코드를 만들면서 fail이 났었는데, 이유는 제가 작성한 리스트는 1부터 시작하는데 인덱스는 0부터 시작하기 때문에 save값을 가져올때 인덱스 범위를 벗어나는 오류가 발생했었고, 마찬가지로 첫번째 행을 나타낼때 j가 1일 때가 아닌 j가 0일때를 생각해줘야해서 코드 작성 초반에 헤맸습니다.

문제를 받고 글로 먼저 작성하고 그 글을 토대로 코드를 짜면 정리가 될 것 같습니다.