[Python] 2676번 라스칼 삼각형

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

2676번: 라스칼 삼각형

---

 

24/02/03

 

 

간단한 수학 문제로, 점화식이 주어져 있다고 DP로 접근한다면 낭패를 볼 수 있는 문제이다.

---

 

문제 접근 방식:

 

 

제한이 $50,000$까지 였기 때문에 2차원 DP로 접근하면 분명히 시간 초과가 날 것이라고 예상했다.

 

따라서 규칙을 찾아야만 했고, 문제에서 주어진 점화식을 $30$까지 돌려봄으로써 일반항을 찾았다.

 

그 값은 $1 + (n-m)m$으로, 만약 규칙을 찾아보려는 접근을 하지 않았더라면 많이 해맸을 것 같은 문제이다.

 

수상할 정도로 범위가 크다면 규칙을 찾아보려는 접근을 먼저 해보자는 좋은 교훈을 얻을 수 있었다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 2676번 라스칼 삼각형
# DP, 수학
'''
접근 방법:
DP로 규칙을 찾아서 일반항을 구하자.
'''
'''
DP = [[0 for _ in range(31)] for _ in range(31)]
for i in range(31):
    DP[i][0] = 1
    DP[i][i] = 1
    for j in range(1, i):
        DP[i][j] = (DP[i-1][j-1] * DP[i-1][j] + 1) // DP[i-2][j-1]
for i in range(31):
    print(*DP[i])
'''
import sys
input = sys.stdin.readline

def R(n, m):
    if n<0 or m<0 or m>n:
        return 0
    if m == 0 or m == n:
        return 1
    a = n-m
    return 1+a*m

for _ in range(int(input())):
    n, m = map(int, input().rstrip().split())
    print(R(n, m))