[BOJ][Python] 16395번 - 파스칼의 삼각형[DP- 실버 5티어]

알고리즘 태그

[DP]

태그 설명

DP 즉, 동적 계획법이란 복잡한 문제를 간단한 여러개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.

 

문제

백준 문제 - 파스칼의 삼각형

링크: 파스칼의 삼각형

문제설명

파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다.
단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다.
N번째 행에는 N개의 수가 있다.첫 번째 행은 1이다.두 번째 행부터, 각 행의 양 끝의 값은 1이고, 나머지 수의 값은 바로 위 행의 인접한 두 수의 합이다.
예를 들어, n=3이면 3번째 행의 2번째 수는 위 행의 인접한 두 수 (1과 1)을 더해서 만든다. 
n=6일 때, 파스칼 삼각형의 6번째 행의 10은 5번째 행의 인접한 두 수(4와 6)을 더해서 구한다. 

 

DP 문제의 키워드는 공통된 규칙?을 찾는것이 제일 중요한것 같다...

점화식을 먼저 구하고 나면 코드로 옮기는것은 쉬운일이기 때문에, 점화식을 먼저 구하려고 노력했다,

아래는 내가 구한 파스칼의 규칙이다

첫번째 예시로 규칙을 찾아보자

1행의 1열: 1

2행의 1: 1, 2행의 2열: 1

3행의 1열: 1, 3행 2열: 2 3행 3열 1

4행의 1열:1 4행 2열: 3, 4행 3열:3, 4행 4열:1

규칙1. 모든 1행은 1이다.

규칙2: 3번째 행렬부터 첫번째와 마지막을 제외한 열의 값은 전행값과 내가 찾고자하는 열의 값에 -1 + 내가 찾고자하는 열의 값이다....

말이 어려우니 아래 수식으로 보자

2행 2열(배열[2][1]) => 배열[1][0] + 배열[1][1]

3행 2열(배열[3][1]) => 배열[2][0] + 배열[2][1]

3행 3열(배열[3][1]) => 배열[2][1] + 배열[2][2]

4행 2열(배열[4][1]) => 배열[3][0] + 배열[3][1]

4행 3열(배열[4][2]) => 배열[3][1] + 배열[3][2]

4행 4열(배열[4][3]) => 배열[3][2] + 배열[3][3]

즉 dp[i][j] = dp[i-1][j] + dp[i-1][j-1]

위와 같은 점화식을 얻을 수 있다.

아래 코드를 보면서 이해해보자

📃 소스코드 및 설명

# 파스칼 삼각형
n, k = list(map(int, input().split()))


dp = [[1]*i for i in range(1, n+1)]
# 점화식 : dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
# 2번째 포문에서 2는 제외 WHY? 맨앞은 1로 고정시키므로
# 2부터 시작하는 이유는 2번째 행까지는 모두 1이므로!
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(dp[n-1][k-1])

처음에 위의 점화식을 적용하기전 삼각형의 행과 열마다 배열을 만들어 주었다.

[

[1]

[1, 1]

[1, 1, 1]

점

점

점

]

몸이 안좋아서 오늘은 조금 대충써야겠다....