코테 준비/DP
[백준] 10844. 쉬운 계단 수
imsmile2000
2023. 2. 5. 02:26
첫 풀이(시간초과....)
def stair(num):
num=list(map(int,str(num)))
for i in range(1,len(num)):
k=abs(num[i]-num[i-1])
if k!=1:
return False
return True
count=0
for i in range(10**(n-1),10**n):
if stair(i)==True:
count+=1
print(count)
정답(인터넷 참고함...)
import sys
n=int(sys.stdin.readline())
dp=[[0]*10 for _ in range(n+1)]
for i in range(1,10):#n이 1일때 (한자리 수일때)
dp[1][i]=1 #1~9 모두 계단수
for i in range(2,n+1): #n이 2이상일때 (두자리 수 이상일때)
for j in range(10):
if j==0: # 0
dp[i][j]=dp[i-1][1]
elif j==9: #2일때 98, 3일때 989, 4일때 9898 ...
dp[i][j]=dp[i-1][8] # 1개
else:
dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])
print(sum(dp[n])%1000000000)