[BOJ] 16395. 파스칼의 삼각형

Python3

문제

https://www.acmicpc.net/problem/16395

키워드

• DP

문제 풀이

• 정수 n과 k가 주어졌을 때 파스칼의 삼각형에 있는 n번째 행에서 k번째 수를 출력하는 프로그램

문제 요구사항

• N번째 행에는 N개의 수가 있다.
• 첫 번째 행은 1이다.
• 두 번째 행부터, 각 행의 양 끝의 값은 1이고, 나머지 수의 값은 바로 위 행의 인접한 두 수의 합이다.
• 수는 이항계수 C(n-1,k-1)이다.

변수 및 함수 설명

• n: n번째 행을 의미하는 변수이다.
• k: n번째 행 중 k번째 수를 의미한다.
• ans: 파스칼 삼각형을 담는 2차원 리스트이다.
  [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], ..]

풀이

• [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], ..] 로 채워진다.
  => 2차원 배열이 필요하다.
• 배열은 처음과 끝 인덱스는 1로 채워지고, 중간 인덱스는 다음 식을 계산해 들어간다.

  ans[i][j] = ans[i-1][j-1] + ans[i-1][j]

(입력 및 선언)

• 사용자로부터 n, k 입력받기
• 1로 초기화된 2차원 리스트 만들기 (크기: i개씩 총 30개)

(반복문)

• 처음과 끝 인덱스에 1 넣기 (생략 가능)
• 중간 인덱스 계산해서 값 넣기

(최종 출력)

• n-1, k-1번째 숫자 출력하기

처음에 문제를 보고 푼 코드이다.

n, k = map(int, input().split())
ans = [[1 for _ in range(i)] for i in range(1, 31)]

for i in range(1, n):
    for j in range(i):
        if j == 0 or j == i:
            ans[i][j] = 1
        else:
            ans[i][j] = ans[i-1][j-1] + ans[i-1][j]
            
print(ans[n-1][k-1])

이 코드의 수행 시간이 아래 코드(44ms)보다 4ms 정도 더 빠르긴 했지만, 가독성 측면에서 아래 코드가 더 좋은 것 같다. 다른 코드를 참고해 수정해보았다.

최종 코드

n, k = map(int, input().split())
ans = [[1 for _ in range(i)] for i in range(1, 31)]

for i in range(2, 30):
    for j in range(1, i):
         ans[i][j] = ans[i-1][j-1] + ans[i-1][j]
            
print(ans[n-1][k-1])

이미 1로 리스트를 초기화했기 때문에 굳이 처음과 끝 인덱스를 신경 쓸 필요가 없다.