백준 10844번 쉬운 계단 수 Python

#️⃣ 백준 10844번 쉬운 계단 수 Python

---

문제 설명

문제

45656이라는 숫자를 예로 들어보면, 이 숫자는 모든 인접한 자리 숫자들의 차이가 정확히 1입니다. 4와 5는 차이가 1이고, 5와 6도 1, 6과 5 역시 차이가 1입니다. 이와 같이 인접한 자리 숫자들의 차이가 모두 1인 수를 "계단 수"라고 정의합니다. 이 문제에서는 정수 N이 주어졌을 때, 길이가 N인 계단 수의 총 개수를 계산해야 합니다. 단, 다음과 같은 조건이 주어집니다.

• 숫자는 0으로 시작할 수 없습니다.
• N은 1 이상 100 이하의 자연수입니다.
• 정답이 매우 클 수 있으므로, 1,000,000,000으로 나눈 나머지를 출력해야 합니다.

---

입력

• 첫째 줄에 정수 N이 주어집니다. (1 ≤ N ≤ 100)

출력

• 길이가 N인 계단 수의 개수를 1,000,000,000으로 나눈 나머지로 출력합니다.

---

테스트케이스

예제 1
입력: 1
출력: 9

예제 2
입력: 2
출력: 17

---

문제설명

예제 1 (입력: 1)
길이가 1인 계단 수는, 0으로 시작할 수 없기 때문에 가능한 숫자는 다음과 같습니다.
1, 2, 3, 4, 5, 6, 7, 8, 9
이들은 모두 한 자리 수이며, 인접한 자릿수가 없기 때문에 차이 조건을 위배하지 않습니다. 따라서 이 9개의 숫자는 모두 계단 수로 인정되며, 정답은 9가 됩니다.

---

예제 2 (입력: 2)
길이가 2인 계단 수는, 각 한 자리 숫자에 대해 1 차이 나는 숫자를 뒤에 붙이는 방식으로 생성됩니다. 예를 들어 1이라는 숫자 뒤에는 0 또는 2만 붙일 수 있고, 2라는 숫자 뒤에는 1 또는 3만 붙일 수 있습니다. 이와 같은 방식으로 가능한 2자리 계단 수들을 모두 나열하면 다음과 같습니다.

• 1에서 시작: 10, 12
• 2에서 시작: 21, 23
• 3에서 시작: 32, 34
• 4에서 시작: 43, 45
• 5에서 시작: 54, 56
• 6에서 시작: 65, 67
• 7에서 시작: 76, 78
• 8에서 시작: 87, 89
• 9에서 시작: 98

이렇게 생성되는 2자리 계단 수는 총 17개이며, 따라서 출력값은 17이 됩니다.

---

✅ 아이디어

---

1. 계단 수는 어떻게 만들어지는가? (순방향 관찰)

▶ 길이 1인 수:

조건상 0으로 시작하는 수는 허용되지 않으므로, 한 자리 수인 1~9는 전부 계단 수가 됩니다.

[1], [2], [3], [4], [5], [6], [7], [8], [9] → 총 9개

---

▶ 길이 2인 수:

각 한 자리 숫자 뒤에는 ±1인 숫자만 붙일 수 있습니다. 예를 들어,

• 1 뒤에는 0 또는 2만 붙일 수 있습니다 → 10, 12
• 2 뒤에는 1 또는 3만 붙일 수 있습니다 → 21, 23
• 3 → 32, 34
• 4 → 43, 45
• 5 → 54, 56
• 6 → 65, 67
• 7 → 76, 78
• 8 → 87, 89
• 9 → 98

이 정보를 표로 정리하면 다음과 같습니다.

🔷 N=1에서 N=2로의 “순방향” 구성표

N=1 끝자리	생성된 N=2 수	N=2 끝자리
1	10, 12	0, 2
2	21, 23	1, 3
3	32, 34	2, 4
4	43, 45	3, 5
5	54, 56	4, 6
6	65, 67	5, 7
7	76, 78	6, 8
8	87, 89	7, 9
9	98	8

이 표에서 알 수 있는 점은 다음과 같습니다.

---

2. 위 표를 바탕으로 역방향 구조를 도출하기

지금까지는 “N=1의 숫자” → “N=2 수” → “N=2의 끝자리”로 앞에서 뒤로 나아갔습니다. 이제는 관점을 바꿔서 N=2의 특정 끝자리를 만들기 위해 어떤 N=1의 숫자가 필요한지 거꾸로 분석합니다.
예를 들어:

• N=2에서 끝자리가 2인 수들은:
  → 12 (N=1의 1에서),
  → 32 (N=1의 3에서)

즉, 끝자리가 2인 수는 N=1의 1과 3에서 만들어집니다. → 이를 통해 다음과 같은 점화식 형태의 원리가 발견됩니다:

`N에서 끝자리 d로 끝나는 수의 개수`는 `N-1에서 끝자리가 d-1이었던 수의 개수` `+ N-1에서 끝자리가 d+1이었던 수의 개수`로부터 만들어진다.

이를 시각적으로 정리하면 다음과 같은 역방향 구성표가 만들어집니다:

🔷 N=2의 끝자리 기준으로 정렬 (역방향)

N=1 끝자리		N=2 끝자리	생성된 수 예시
1		0	10
2		1	21
1		2	12
3			32
2		3	23
4			43
3		4	34
5			54
4		5	45
6			65
5		6	56
7			76
6		7	67
8			87
7		8	78
9			98
8		9	89

※ 주의: 각 줄은 “N=3 끝자리 하나”를 구성하기 위해 N=2에서 어떤 끝자리에서 유도되었는지를 나타냅니다.

---

3. 점화식 구성의 일반화

이제 위에서 관찰한 구조를 일반화할 수 있습니다.

길이가 N이고, 끝자리가 d인 계단 수의 개수를 `dp[N][d]`라고 한다면,

• d = 0일 경우
  → 이전 자리에서는 d = 1에서만 올 수 있습니다.
  → `dp[N][0] = dp[N-1][1]`
• d = 9일 경우
  → 이전 자리에서는 d = 8에서만 올 수 있습니다.
  → `dp[N][9] = dp[N-1][8]`
• 그 외의 경우 (1 ≤ d ≤ 8)
  → d = 1이면: 이전 끝자리 d = 0, 2에서 올 수 있음
  → 즉:
  `dp[N][d] = dp[N-1][d-1] + dp[N-1][d+1]`

---

N=3을 위한 전개 과정

---

1. N=2 계단 수 전체 나열

우선 N=3을 만들기 위해서는, N=2까지 생성된 모든 계단 수를 알아야 합니다. N=1에서 시작한 각 숫자에 대해 ±1 차이가 나는 수를 붙여 다음과 같은 N=2 수들이 생성되었습니다.

10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98

총 17개입니다.

---

2. 각 N=2 수의 끝자리를 기준으로

→ 어떤 숫자를 덧붙이면 N=3 수가 되는지 확인
핵심 논리: 각 계단 수의 “끝자리 숫자”에 ±1인 숫자만 뒤에 붙일 수 있음. 이 원리를 각 수에 적용합니다.

🔹 예시

N=2 수	끝자리	가능한 다음 숫자 (±1)	생성되는 N=3 수
10	0	1	101
12	2	1, 3	121, 123
21	1	0, 2	210, 212
23	3	2, 4	232, 234
32	2	1, 3	321, 323
34	4	3, 5	343, 345
43	3	2, 4	432, 434
45	5	4, 6	454, 456
54	4	3, 5	543, 545
56	6	5, 7	565, 567
65	5	4, 6	654, 656
67	7	6, 8	676, 678
76	6	5, 7	765, 767
78	8	7, 9	876, 878
87	7	6, 8	876, 878
89	9	8	898
98	8	7, 9	987, 989

---

3. N=3 수들을 끝자리 기준으로 정렬

이제 생성된 N=3 수들을 → 그 끝자리에 따라 묶어서 분류합니다. 이 과정을 통해, N=3의 끝자리 d에 도달하려면 N=2에서 어떤 끝자리 d'에서 왔는지를 추적할 수 있게 됩니다.

---

4. 표로 정리 (역방향 도출 구조)

아래는 N=3에서 끝자리가 0~9인 계단 수들이 → N=2의 어떤 수에서 나왔는지를 역방향으로 구조화한 표입니다. 이 표가 바로 점화식이 도출되는 구조입니다.

N=2 끝자리 (출발)		N=3 끝자리	생성된 수 예시
1		0	210
0		1	101
2			321
1		2	212
3			232
2		3	123
4			343
3		4	234
5			454
4		5	345
6			565
5		6	456
7			676
6		7	567
8			876
7		8	678
9			898
8		9	989

※ 주의: 각 줄은 “N=3 끝자리 하나”를 구성하기 위해 N=2에서 어떤 끝자리에서 유도되었는지를 나타냅니다.

---

5. 이 표에서 점화식 발견

이제 위 표를 바탕으로 “끝자리가 d인 N=3 수는, 끝자리가 d-1 또는 d+1인 N=2 수로부터 만들어질 수 있다.”는 점화식 규칙을 명확히 볼 수 있습니다.
정리:

• `dp[3][d] = dp[2][d-1] + dp[2][d+1]`
  (단, d = 0일 때는 `dp[3][0] = dp[2][1]`, d = 9일 때는 `dp[3][9] = dp[2][8]`)

---

✅ 전체코드

N=int(input())

dp=[[0 for _ in range(10)] for _ in range(N+1)]

# 길이가 1인 계단 수 초기값 설정
# 0으로 시작할 수 없으므로 dp[1][0]은 0
for i in range(1,10):
    dp[1][i]=1

# 길이가 2부터 N까지의 계단 수 계산
for i in range(2,N+1):
    for j in range(10):
        if j==0: # 끝자리가 0인 경우, 이전 자리(i-1)는 반드시 1이어야 함
            dp[i][j]=dp[i-1][j+1]
        elif j==9: # 끝자리가 9인 경우, 이전 자리(i-1)는 반드시 8이어야 함
            dp[i][j]=dp[i-1][j-1]
        else: # 끝자리가 1부터 8인 경우, 이전 자리(i-1)는 j-1 또는 j+1일 수 있음
            dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]

# 길이가 N인 모든 계단 수의 합 계산 및 1,000,000,000으로 나눈 나머지 출력
print(sum(dp[N])% 1000000000)

---

✅ 개별코드

N=1 초기값 세팅

• 0으로 시작할 수 없기 때문에 `dp[1][0] = 0`
• 나머지 1~9까지는 `dp[1][i] = 1`

끝자리	0	1	2	3	4	5	6	7	8	9
N=1	0	1	1	1	1	1	1	1	1	1

---

N=2 값 계산 (점화식 적용)

끝자리 j	계산식	값
0	dp[1][1]	1
1	dp[1][0] + dp[1][2]	0+1 = 1
2	dp[1][1] + dp[1][3]	1+1 = 2
3	dp[1][2] + dp[1][4]	1+1 = 2
4	dp[1][3] + dp[1][5]	1+1 = 2
5	dp[1][4] + dp[1][6]	1+1 = 2
6	dp[1][5] + dp[1][7]	1+1 = 2
7	dp[1][6] + dp[1][8]	1+1 = 2
8	dp[1][7] + dp[1][9]	1+1 = 2
9	dp[1][8]	1

끝자리	0	1	2	3	4	5	6	7	8	9
N=2	1	1	2	2	2	2	2	2	2	1

---

N=3 값 계산 과정 일부 (예시)

• j=0: `dp[3][0] = dp[2][1] = 1`
• j=1: `dp[3][1] = dp[2][0] + dp[2][2] = 1 + 2 = 3`
• j=2: `dp[3][2] = dp[2][1] + dp[2][3] = 1 + 2 = 3`
• ...

끝자리	0	1	2	3	4	5	6	7	8	9
N=3	1	3	3	4	4	4	4	4	3	2

---

✅ 결론

• `dp[N][j]`는 길이가 N이고 끝자리가 j인 계단 수의 개수를 저장하는 배열입니다.
• 점화식은 끝자리 j에 대해 이전 단계에서 j±1을 확인해 값을 누적합니다.
• 이 규칙은 수의 자리 수가 증가함에 따라 반복 적용됩니다.
• 최종 결과는 `dp[N][0] + dp[N][1] + ... + dp[N][9]`의 합이며, MOD로 나눈 나머지를 출력합니다.

---