[C++/Python] 백준 10844 - 쉬운 계단 수

문제 링크

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

10844번: 쉬운 계단 수

 

 

N이 1일 때는 1부터 9까지 총 9가지 계단이 있습니다.

N이 2일 때 부터는 오른쪽 숫자를 기준으로

0일 때는 왼쪽에서 1 밖에 오지 못하므로 10 한개

1~8일 때는 (21, 31), (12, 32), (23, 43), ... 과 같이 왼쪽에서 -1과 +1의 숫자가 올 수 있습니다.

9일 때는 왼쪽에서 8 밖에 오지 못하므로 89 한개로 완성됩니다.

 

따라서 다음 점화식으로 총 계단 수를 구할 수 있습니다.

d[N][M] (M = 0~9) = 

if M = 0 then d[N-1][M+1]

if M = 9 then d[N-1][M-1]

else d[N-1][M-1] + d[N-1][M+1]

 

그리고 주의해야 할 점은 d[N][0]은 위의 그림처럼 첫 번째 값이 0부터 시작하는 방법의 갯수인데

문제에서는 0부터 시작하는 방법은 없다고 명시되어 있으므로 d[N][0]을 제외시켜줍니다.

 

구현 코드