[BOJ][Python] 백준 10844번 - 쉬운 계단 수

문제 링크: https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

 

---

문제 풀이

1자리인 경우는 1~9이므로 9개이다.

dp[N][P]로 배열을 만들껀데 N은 수의 길이, P는 일의 자리의 숫자를 뜻한다. 물론 N자리이며 일의 자리 숫자가 P인 개수를 저장할 것이다. 예를 들어 87은 dp[2][7]에 속한다. 67도 마찬가지이다. 즉, dp[2][7] = 2라는 것이다.

 

왜 일의 자리 숫자의 정보를 이용하는 지 생각해보자. 예를 들어 1232가 있는데 이 수를 이용해 (N+1)자리의 숫자를 만드려면 12321 혹은 12323을 생각해볼 수 있겠다. 일의 자리 숫자에서 +1 혹은 -1을 해서 계단 수인 (N+1)자리를 만들 수 있다. 하지만 예외가 있다. 만약 P=0이라면 -1을 할 수 없고, P=9라면 +1을 할 수 없기 때문에 이 부분만 예외적으로 처리해주자.

 

마지막으로, 길이가 N인 계단 수가 몇 개인지 물었으므로, 일의 자리가 0부터 9까지인 모든 계단 수를 더해주면 된다.

 

 

코드