[파이썬/백준 10844번] 쉬운 계단수

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

 

하루 종일 푼 것 같다.

결국 엑셀로 5자리수 까지 해 보고 풀 수 있었던..

노가다의 산물

 

근데 이 전에 있었던 정수삼각형이나 RGB거리와 비슷한 문제인 것 같다는 생각이 들었다.

 

N=int(input())
dp=[[0 for _ in range(10)] for _ in range(N+1)]
dp[1]=[0,1,1,1,1,1,1,1,1,1]
for i in range(2,N+1):
	for j in range(10):
		if j==0:
			dp[i][j]=dp[i-1][1]
		elif j==9:
			dp[i][j]=dp[i-1][8]
		else:
			dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])%1000000000
			
sdp=sum(dp[N])%1000000000

print(sdp)

뭔가 내 힘으로 푼 것 같아서 

정말 정말 정말 뿌듯하다