Search

[백준 10844] 쉬운 계단 수

[백준 10844] 쉬운 계단 수

Tip

2차원 DP 테이블 구성
d[n의 수][n자리 숫자일 때 해당 숫자 앞에 올 수 있는 숫자]
점화식
뒷자리가 0인 경우 앞에 1만 가능
d[i][j] = d[i - 1][j + 1]
뒷자리가 9인 경우 앞에 8만 가능
d[i][j] = d[i - 1][j - 1]
뒷자리가 1~8인 경우 앞에 숫자는 2개씩 가능
d[i][j] = d[i - 1][j - 1] + d[i - 1][j + 1]

풀이 소스 코드

import sys si = sys.stdin.readline n = int(si()) d = [[0] * 10 for _ in range(n + 1)] # 1 자리수는 0을 제외하고(조거 : 0은 앞에 올 수 없음) 1로 초기화 for i in range(1,10): d[1][i] = 1 # d[n 자리 수][n자리 숫자일 때 해당 인덱스 앞에 올 수 있는 숫자] for i in range(2, n + 1): for j in range(10): # 뒷자리가 0일 때는 앞에 1밖에 오지 못함 if j == 0: d[i][j] = d[i - 1][j + 1] # 뒷자리가 9일 때는 앞에 8밖에 오지 못함 elif j == 9: d[i][j] = d[i - 1][j - 1] # 뒷자리가 1~8일 때는 앞에 숫자가 2개씩 올 수 있음 else: d[i][j] = d[i - 1][j - 1] + d[i - 1][j + 1] print(sum(d[n]) % 1000000000)
Python