[백준_2688] 줄어들지 않아 python

처음에 리커전으로 모든 경우의수를 조사해야하나 생각했다.

그러나 오히려 그렇게 해결하면,

각 자리수를 비교해야하며,

두자릿수 기준 00 같은 수의 처리가 애매해지는 문제가 발생해 오히려 더 귀찮아질 것 같았고

시간복잡도 측면에서 찜찜한 느낌도 들었다.

결국 결론은 2차원 배열을 이용한 dp였다.

이젠 좀 dp가 익숙해진 느낌?

# dp 설계

dp = [

　[0] * 10 for _ in range(64 + 1)

]

# 초기 설정

for i in range(10):

　dp[1][i] = 1

for i in range(1, 65):

　dp[i][0] = 1

# dp 채워넣기

for i in range(2, 65):

　for j in range(1, 10):

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

# t 입력

t = int(input())

for _ in range(t):

 

　# n 입력

　n = int(input())

　# 출력

　print(sum(dp[n]))