[백준] 10844: 쉬운 계단 수 파이썬 리뷰

10844번: 쉬운 계단 수

풀이 방법은 해당 블로그를 참조하자

 

dp 테이블을 각 자리수 마다 한줄 씩 2차원 배열로 설정한다. (행 : 자릿 수, 열 : 0~9)

테이블에는 해당 숫자가 맨 앞에 있을 때 가능한 경우의 수를 저장한다.

 

예를 들어, dp[2][1]에는 백의 자리 숫자가 1인 경우의 수가 저장돼있다. 101, 121, 123

 

 

https://dev-wd.github.io/algorithm/backjoon10844/

dp[2][1]을 저장했을 때를 생각해보자, dp[1][0]과 dp[1][2]를 더한 값이 dp[2][1]에 저장된다.

맨 앞의 숫자가 1이라면 그 뒤에 올 수 있는 숫자는 당연히 0 또는 2이다.

 

2이 맨 앞에 있을 때 경우의 수는 dp[1][2]에 저장 돼 있다.

0이 맨 앞에 있을 때 경우의 수 또한 dp[1][0]에 저장 돼 있다.

 

여기서 0이 맨 앞에 있을 때 경우의 수 dp[i][0]를 저장하는 이유를 알 수 있다. 다음 단계에서 사용 되기 때문이다.

 

답을 낼 때는 해당 자릿 수의 모든 값을 더하는데, 0을 제외한다. 0은 맨 앞자리에 올 수 없기 때문이다.