[10844] 쉬운 계단 수

😲 문제

출처
45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력
1
출력
9

입력
2
출력
17

❗️ 문제 재정의

1. 입력 길이당 계단수를 구하시오.
2. 계단 수는 각 인접한 자리의 숫자가 단 "1"씩 차이나는 숫자를 의미한다.

이런 문제의 경우는 규칙을 찾아야 하는데
간단하게 생각하자면 문제의 접근 방법은 총 두가지가 있겠다.

• 시작하는 수로 경우의 수를 나눌 것인가
• 끝나는 수로 경우의 수를 나눌 것인가

먼저 시작하는 수로 경우의 수를 나눠보자

2자리 수의 경우
10 12 
21 23 
32 34 
43 45 
54 56 
65 67 
76 78 
87 89 
   98 
   
3자리 수의 경우
   101 121 123 
210 212 232 234 
321 323 343 345
432 434 454 456 
543 545 565 567
654 656 676 678
765 767 787 789
876 878 898 
987 989
...

음 어느 특정한 규칙이 있을 수도 있지만 난 발견하지 못했다.
그렇다면 이제 끝나는 수로 경우의 수를 나눠보자

2자리 수
10
21
12 32
23 43
34 54
45 65
56 76
67 87
78 98
89

3자리 수
			210
    101 121 321
    212 232 432
123 323 343 543
234 434 454 654
345 545 565 765
456 656 676 876
567 767 787 987
678 878 898 
789 989

끝나는 수는 0과 9을 제외해보면 특정한 규칙이 발생되게 된다.
1~8까지의 수는 전 레벨의 -1인 수와 전 레벨의 +1인 수의 합으로 이루어진다.
즉, 길이가 3인 8이라면 길이가 2인 7과 길이가 2인 9의 합이다.
그렇다면 0은 어떤 경우로 이루어질까?
그 전 레벨이 1로 끝나는 수는 0으로 끝날 수 있다.
마지막으로 9는 어떤 경우로 이루어질까?
그 전 레벨이 8로 끝나는 수는 9로 끝날 수 있게 된다.

✔ 계획 수립

1. 0으로 끝나는 것들은 1로 끝나는 전 레벨의 것들의 개수임.
2. 9으로 끝나는 것들은 8로 끝나는 전 레벨의 것들의 개수임.
3. 나머지 숫자는 그 전 레벨의 -1, +1로 끝나는 것들의 개수의 합
   ex) 길이가 3인 8이라면 길이가 2인 7과 길이가 2인 9의 합

dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

2차원 dp 배열을 만들고 각 길이당 끝나는 숫자를 사용하면서 증가하도록 한다.
그리고 n길이가 된다면 그 배열의 합을 출력하면 된다.

출력은 저 합에서 1,000,000,000으로 나눈 나머지를 출력해야한다.

👨🏻‍💻 문제 풀이

n = int(input()) # 최종 자릿수

# 한 행에는 0~9까지의 수
# 행의 수는 0~n으로 n+1 이 된다.
# dp 배열 초기화
dp = [[0] * 10 for _ in range(n+1)]

# 1자리수 초기화 무조건 계단 수의 길이는 1임.
for i in range(10):
    dp[1][i] =  1
dp[1][0] = 0 # 0으로 시작하는 수는 없다.
# 길이가 2 이상인 계단 수의 경우의 수
for i in range(2,n+1):
    for j in range(10):
        if j==0: # 끝자리가 0인 계단 수는 전 레벨의 끝자리가 1인 계단수의 경우의 수이다.
            dp[i][0] = dp[i-1][1]
        elif j==9: # 끝자리가 9인 계단 수는 전 레벨의 끝자리가 8인 계단수의 경우의 수이다.
            dp[i][9] = dp[i-1][8]
        else:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

print(sum(dp[n])%1000000000)

😅 회고

아직 규칙을 찾는 문제가 어색하다. 꽤나 시간이 소요됐었다.
나름 이 문제는 명확하게 규칙을 찾으라고 제시한 꼴인데도 말이다..ㅠ
어떻게 규칙을 찾을지 케이스를 나누고
해당 케이스에서 바텀업으로 규칙을 만들어본 후 규칙이 안보인다면 다음 케이스로 넘어가는 방식으로 하는데 눈썰미가 그리 좋진 않아서 한번에 규칙이 보이진 않는다.
좀 더 논리적으로 접근하는 것을 연습해야겠다....

dp[1][0] = 0의 조건을 깜빡했었다. 0으로 시작하는 수는 없다고 공표했음에도 이를 적용치 않고 진행했었다. 문제를 자세히.. 읽자...