[BaekJoon] 백준 16395 파스칼의 삼각형 (Python / 파이썬)

BaekJoon 백준 16395 파스칼의 삼각형 문제는 파스칼의 삼각형은 이항 계수를 삼각형 형태로 배열한 것인데, 파스칼의 삼각형에 있는 n번째 행에서 k번째 수를 구하는 문제다. DP Dynamic Programming 동적 계획법 알고리즘 활용 문제로 난이도는 Bronze 1다.

 

BaekJoon 16395 파스칼의 삼각형 문제 정보

출처

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

알고리즘 분류

- 다이나믹 프로그래밍 DP 동적 계획법, 수학, 조합론

DP Dynamic Programming 동적 계획법 알고리즘과 예제

DP Dynamic Programming 동적 계획법 알고리즘과 예제

난이도

- 브론즈 1 / Bronze 1

 

파스칼의 삼각형 문제 요약

• 파스칼의 삼각형은 이항 계수를 삼각형 형태로 배열한 것인데, 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다.
  1. N번째 행에는 N개의 수가 있다.
  2. 첫 번째 행은 1이다.
  3. 두 번째 행부터, 각 행의 양 끝의 값은 1이고, 나머지 수의 값은 바로 위 행의 인접한 두 수의 합이다.
• 정수 n과 k가 주어졌을 때 파스칼의 삼각형에 있는 n번째 행에서 k번째 수를 구하여 출력한다. (1 ≤ k ≤ n ≤ 30)
• 이때, 이 수는 이항 계수 C(n-1, k-1) 임에 주의하시오.

 

문제 풀이 과정

1. 주어진 행 n 만큼 반복한다.
2. 행의 숫자들을 구하기 위해 행의 숫자 개수만큼(n) 반복하여
3. 각 행의 처음과 끝이라면 row에 1을 저장하고
4. 나머지 자리에는 바로 위 행의 인접한 두 수의 합을 저장한다.
5. 행의 숫자들을 dp에 저장한다.
6. 행의 수만큼 3~5를 반복한다.
7. dp에 행별 파스칼 삼각형의 숫자들이 저장되어있으므로 n행의 k번째 수를 출력한다.

 

코드 및 설명

• row - 각 행의 숫자들을 담은 list
• dp - idx+1번째 행의 숫자들을 저장한 list

n, k = map(int, input().split())
dp = []
for i in range(n):
    row = []
    for j in range(i + 1):
        # 각 행의 처음, 마지막 값은 1
        if j == 0 or j == i:
            row.append(1)
            # print(1, end=' ')
        # 위 행의 인접한 두 수의 합
        else:
            row.append(dp[i - 1][j - 1] + dp[i - 1][j])
            # print(dp[i - 1][j - 1] + dp[i - 1][j], end=' ')
    dp.append(row)
    # print()

print(f'{dp[n - 1][k - 1]}')

---

BaekJoon 백준 16395 파스칼의 삼각형 문제를 파이썬 python DP Dynamic Programming 동적 계획법 알고리즘으로 풀어보았다. 난이도는 Bronze 브론즈 1이다.