[백준 10844번] 쉬운 계단 수 (python)

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

 

기록

(dp 7일차) 도저히 반복문으로 푸는 방법을 모르겠어서 재귀로 구현했다. 재귀가 훨씬 이해하기는 쉬운 것 같다. 참고로 1000000000으로 나눈 나머지 구하라길래 1e9로 나눴는데 틀렸다고 나왔다. 그래서 실수여서 그런가 싶어서 정수로 바꿔서 출력했는데도 틀렸다. 결국 1000000000으로 나머지 구해서 성공...

 

각 숫자로 시작하는 길이가 N인 계단 수 개수를 dp에 저장하여 재귀적으로 탐색하며 메모이제이션을 사용하여 구현했다.

ex) dp[5][3] 5로 시작하는 3자리 계단 수의 개수

 

코드

N = int(input())

dp = [[0]*(N+1) for i in range(10)]
def stair(now, l):
    if now<0 or now>9: return 0
    if l<=1 : return 1
    if dp[now][l] : return dp[now][l]
    dp[now][l] = stair(now-1,l-1)+stair(now+1, l-1)
    return dp[now][l]

total = 0
for i in range(1, 10):
    total += stair(i, N)
print(total%1000000000)

1. 각 숫자로 시작하는 길이가 N인 계단 수 개수를 저장할 2차원배열 dp 생성

2. stair 함수는 시작숫자로 시작하는 길이가 N인 계단 수의 개수를 반환하는 함수로, 메모이제이션 방법을 사용하여 각 함수의 결과를 dp배열에 저장한다.

3. 1부터 9까지의 시작숫자를 인자로 넣어 결과를 총합하여 반환한다.