[10844] 쉬운 계단수

문제 설명

---

길이가 N인 계단 수의 개수를 구하는 문제이다. 계단 수란, 0으로 시작하지 않으며, 인접한 모든 자리의 차이가 정확히 1인 수를 의미한다.

예를 들어, N=2일 때 가능한 계단 수는 다음과 같다.

• 길이 2의 계단 수: 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98
• 총 개수는 17개이다.

🔹 문제 요구사항

• N이 주어졌을 때, 길이가 N인 계단 수의 개수를 10^9로 나눈 나머지를 출력해야 한다.

문제 풀이

---

동적 계획법과 재귀를 이용해 해결해야 한다.

동적 계획법(DP)과 메모이제이션의 활용

DP 테이블의 정의

• dp[loc][val]
  dp[loc][val]_은 **길이가 loc이고 마지막 자릿수가 val인 계단 수의 개수_를 의미한다.
  기저 조건으로, 길이가 1인 수는 모든 한 자릿수 수가 계단 수이므로 _dp[1][i] = 1 (0 ≤ i ≤ 9)로 초기화된다.

재귀 함수를 통한 점화식 구현

코드의 핵심은 recursion(loc, val) 메서드에 있다. 이 메서드는 다음과 같은 방식으로 동작한다.

1. 기저 조건

   • loc == 1인 경우, 이미 초기화된 값을 반환한다.
     이때, 길이가 1이면 해당 자릿수의 계단 수는 1개이다.

2. 메모이제이션 검사

   • _dp[loc][val]_의 값이 아직 계산되지 않았다면(null인 경우) 아래의 점화식을 통해 값을 구한다.
     이를 통해 중복 계산을 방지하여 효율성을 높인다.

3. 점화식(상태 전이)

   • 자릿수가 0인 경우:
     0은 바로 이전 자릿수가 1이어야 하므로,

     dp[loc][0] = recursion(loc-1, 1);

     이와 같이 계산된다.

   • 자릿수가 9인 경우:
     9는 바로 이전 자릿수가 8이어야 하므로,

     dp[loc][9] = recursion(loc-1, 8);

     로 처리된다.

   • 자릿수가 1 ~ 8인 경우:
     일반적으로, 인접 자릿수는 현재 자릿수보다 1 작은 값과 1 큰 값이어야 하므로,

     dp[loc][val] = recursion(loc-1, val-1) + recursion(loc-1, val+1);

     와 같이 두 경우의 합으로 점화식을 구성한다.

4. 모듈로 연산

   • 각 재귀 호출의 결과는 MOD(10^9)로 나눈 나머지를 반환한다.
     이는 문제에서 정답이 매우 클 수 있으므로 모듈러 연산을 적용한 것이다.

최종 결과 도출

• 결과 계산:
  메인 함수에서는 길이가 n인 수 중에서 맨 앞자리가 0이 아닌 계단 수의 개수를 구하기 위해,
  1부터 9까지의 마지막 자릿수를 가진 경우의 수를 모두 합산한다.
  이때, recursion(n, i)를 호출하여 각 경우의 수를 구한 후 합산하고 결과를 출력한다.

소감

---

DP의 Top-Down 방식을 적용해서 풀었다. 역시 아직 DP가 익숙하지 않아. 다른 분의 설명을 참고하였다. 앞으로 DP 문제를 더 다양하게 풀어보고 더 익숙해져야겠다.