파스칼의 삼각형

https://koreanraichu.tistory.com/802

백준 11050번 풀이

여기서 이항계수 얘기를 했는데, 이항계수 하면 따라오는 게 바로 파스칼의 삼각형이다.

 

이거 말하는거 맞다.

 

파스칼의 삼각형-규칙

1. 꼭대기에는 1이 하나 있다.

2. 그 밑으로는 양 옆의 숫자를 더해야 하는데 두번째 줄은 더할게 없어서 1 두개다. 

3. 그 밑으로는 양 사이드에 1을 쓰고, 순차적으로 윗줄 양 옆의 수를 더한다. 그래서 3번째 줄은 1+1=2다. 

4. 이하 반복. 

 

토대 잡기

import sys

N = int(sys.stdin.readline())

# 첫번째 줄: 1
# 두번쨰 줄: 1, 1
# 세번째 줄: 1, 1+1, 1
# 네번째 줄: 1, 1+1+1. 1+1+1, 1
triangle = []

for i in range(N):
    print(i)

일단 여기는 뭐 볼 거 없으니까 빠르게 다음으로 넘어가자.

 

삼각형 만들기

for i in range(N):
    # range는 0부터 시작하기때문에 i도 0부터 시작한다. 
    # 그리고 각 행은 i+1개의 열을 갖는다. (꼭대기: i=0, 열 수=1)
    rows = [1] * (i + 1)
    print(rows)

여기서부터 잘 따라오십쇼.

 

일단 왜 i+1이냐... 답은 간단하다. python의 range는 시발점을 지정하지 않으면 0부터 시작이거든... 인덱싱도 다 0부터 시작이다. 그래서 1을 안 더하면 어떻게 되냐고? 맨 위층에 꼭지점이 안 생김. 그렇게 되면 N이 5일때 4까지만 나온다.

 

[1]
[1, 1]
[1, 1, 1]
[1, 1, 1, 1]
[1, 1, 1, 1, 1]

1만 들어있다고? 지금은 삼각형 형태만 만든거니까 1만 들어있는 게 정상이다.

 

내용물 채우기

다 왔으니까 좀만 더 참으십쇼. 이제 삼각형 뼈대를 만들었으니까 안에 내용물만 채우면 된다.

 

for i in range(N):
    # range는 0부터 시작하기때문에 i도 0부터 시작한다. 
    # 그리고 각 행은 i+1개의 열을 갖는다. (꼭대기: i=0, 열 수=1)
    rows = [1] * (i + 1)
    for j in range(1,i):
        # 그럼 이제 저 1만 있는 삼각형들의 안쪽을 채워볼까요?
        # 가장 바깥을 제외한 안쪽은 위 행에서 인접한 좌우의 요소들을 더해서 값을 구한다. 
        rows[j] = triangle[i-1][j-1] + triangle[i-1][j]
    triangle.append(rows)

print(*triangle)

주석 빼면 다섯줄밖에 안됨. 출력 빼면 네줄인데 이걸로 삼각형 내용물을 채울 수 있다. 위에서 우리가 뼈대를 만들었잖아요? 그럼 만든 뼈대를 채워야 하지 않겠음? 뼈대를 채우기 위해서는 내 위층에서 나랑 인접한 값(내 위에 양 옆에 둘)이 뭔지를 알아야 할 것 아닙니까. 그죠?

 

rows[1] = triangle[0][1] + triangle[0][1] # j = 1 
rows[2] = triangle[1][1] + triangle[1][2] # j = 2

i가 1... 그니까 한줄일때는 쟤가 안 돌아간다. j가 1 이상 1 미만이 가능하겠수? 무슨 유니콘의 뿔도 아니고. 그래서 i가 2일때부터 j가 작동한다고 보시는 게 낫습니다. 그러면 j가 1일때 첫번째 열(인덱싱은 0부터라 맨 꼭대기는 rows[0]임)의 첫번째와 두번째를 더해야되는데 하나밖에 없으니까 1만 두 개 나온다. 그럼 그 밑에는요? 두번째열에 1 두개니까 그거 더하면 2죠. 양 옆은 더할 거 없으니까 1인거고.

 

import sys

N = int(sys.stdin.readline())

# 첫번째 줄: 1
# 두번쨰 줄: 1, 1
# 세번째 줄: 1, 1+1, 1
# 네번째 줄: 1, 1+1+1. 1+1+1, 1
triangle = []

for i in range(N):
    # range는 0부터 시작하기때문에 i도 0부터 시작한다. 
    # 그리고 각 행은 i+1개의 열을 갖는다. (꼭대기: i=0, 열 수=1)
    rows = [1] * (i + 1)
    for j in range(1,i):
        # 그럼 이제 저 1만 있는 삼각형들의 안쪽을 채워볼까요?
        # 가장 바깥을 제외한 안쪽은 위 행에서 인접한 좌우의 요소들을 더해서 값을 구한다. 
        rows[j] = triangle[i-1][j-1] + triangle[i-1][j]
    triangle.append(rows)

# 이거 이차원 배열이라 이렇게 안 하면 일렬로 나옴...
print(*triangle, sep="\n")

그래서 이건데... 출력에 왜 언패킹이 되어 있나요? 저게 이차원 배열입니다. 그래서 언패킹+구분자 없으면 대괄호 두개가 쌩으로 나오고요. 언패킹 해도 구분자 설정 안 하면 일렬로 나옵니다.