백준 10844번 쉬운 계단 수

문제

문제 출처 : https://www.acmicpc.net/problem/10844

풀이 과정

첫 째 자리는 1~9가 올수있고

1이 온다면 둘 째 자리수는 0과 2가 올 수 있다.

9가 온다면 8만이 올 수 있다.

둘 째 자리 수가 0이라면 셋 째 자리수는 1만 올 수 있다.

그러므로 점화식은

i =    0    => dp[N][i] = dp[N - 1][i + 1]

i = (1 ~ 8) => dp[N][i] = dp[N - 1][i - 1] + dp[N - 1][i + 1]

i =    9    => dp[N][i] = dp[N - 1][i - 1]

로 나타낼 수 있다.

이를 동적계획법으로 풀면 된다.

C++ 소스코드

중간에 나머지 계산을 해주는 이유는, 점화식을 통해 합을 계산하는 경우에도

type 범위를 초과해서 원치 않는 값을 배열에 저장하는 경우가 발생하기 떄문