[BOJ, 백준] 2676 라스칼 삼각형 Python

 

 

주어진 문제는 위와 같다.

이 문제를 풀면서 중요한 점이 2가지 있는데, 이것을 생각해보자.

 

첫번째로, $R(n,m)$을 계산함에 있어 $if m > n$ then $R(n,m) = 0$ 이라는 점이겠다.

두번째로, 문제에서 주어진 식인 $R(n+1, m+1) = (R(n,m) \cdot R(n,m +1) + 1) / R(n-1, m)$

 

여기서, $R(n,m)$가 사실은 다음과 같은 모양을 하고 있다고 가정해보자. 

$$ R(n, m) = (n - m) \cdot m + 1$$

 

이러한 식을 세웠다면 먼저 검증해야할 것이 있다. 소위 말하는 수학적 귀납법이 되겠다.

i) 초기 조건에서 성립하는지?

ii) 임의의 상황에서도 성립하는지?

 

초기조건인 $n = 0, m = 0$에서는 자명하게 성립하는 것을 알 수 있다.

그렇다면 임의의 $n, m$에 대해서는 어떨까?

 

여기서는 일반성을 잃지 않고, $n-1 >= m$ 이라고 가정하자.  만약, $n - 1 < m$이라는 것은, $n < m + 1$ 꼴인데,

첫번째 조건에서 $m > n$이라면 $R(n,m) = 0$이라는 것을 알 수 있고, 해당 되는 케이스는 $n = m$ 뿐인데, 이건 1로 자명하기 때문.

 

그렇다면, 식을 실제로 검증해보자. $$\frac{1 + R(n,m) \cdot R(n,m +1)}{R(n-1, m)}  = \frac{1 + ((n - m)m + 1) \cdot ((n-m-1) \cdot (m+1) + 1)} {(n-1-m)\cdot m  + 1} $$

 

여기서, 분모인 $(n-1-m)\cdot m  + 1$를 $X$로 치환하게 되면, 분자의 부분은 다음과 같이 나타낼 수 있다

\[
\begin{aligned}
    &((n - m)m + 1) \cdot ((n-m-1) \cdot (m+1) + 1) \\
    &= (X + m)(X + n - m - 1) + 1 \\
    &= X^2 + (n - 1)X + m(n-m-1) + 1 \\
    &= X^2 + (n - 1)X + (X-1) + 1 \\
    &= X^2 + nX.
\end{aligned}
\]

그러므로, $$\frac{X^2 + nX}{X} = X + n =n(m+1) -m (m+1) + 1 = (n-m) (m+1) + 1 = R(n+1, m+1)$$

이렇게 나타내어지는 것을 알 수 있겠다.

 

위의 과정을 통해, 수학적 귀납법이 허용된다는 것을 알았으니, 해답 코드는 다음과 같이 간단하게 쓰일 수 있겠다.

 

import sys
input = sys.stdin.readline

T = int(input())
for _ in range (T):
    n, m = map(int,input().split())
    print((n-m) * m + 1)