-
[백준 10844번] 쉬운 계단 수Coding Test/백준 2021. 1. 25. 21:21
# 문제
내 풀이
# 내 풀이 n = int(input()) # 자리수마다 가장 뒤에 오는 숫자 0 ~ 9를 고려하는 DP 테이블 생성 dp = [[0] * 10 for _ in range(101)] # DP 테이블 초기화 for i in range(1, 10): dp[1][i] = 1 # 바텀업 다이나믹 프로그래밍 수행 for i in range(2, 101): # 0과 9에 대해 점화식 수행 dp[i][0] = dp[i - 1][1] dp[i][9] = dp[i - 1][8] # 1 ~ 8까지의 점화식 수행 for j in range(1, 9): dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1] # 결과 출력 print(sum(dp[n]) % int(1e9))
'Coding Test > 백준' 카테고리의 다른 글
[백준 2156번] 포도주 시식 (0) 2021.01.30 [백준 1181번] 단어 정렬 (0) 2021.01.27 [백준 1463번] 1로 만들기 (0) 2021.01.24 [백준 2579번] 계단 오르기 (0) 2021.01.23 [백준 1149번] RGB거리 (0) 2021.01.22