문제

https://www.acmicpc.net/problem/10844

요구사항 분석

• N-자리 계단 수의 개수
• 계단 수: 인접한 자리 숫자의 차이가 1인 숫자

핵심단서

• 인접한 자리 숫자 간의 관계

  • N자리 숫자의 끝자리가 0인 경우 바로 앞자리 숫자는 1 만 가능
  • N자리 숫자의 끝자리가 1인 경우, 바로 앞자리 숫자는 0 또는 2
  • N자리 숫자의 끝자리가 5인 경우, 바로 앞자리 숫자는 4 또는 6
  • N자리 숫자의 끝자리가 j인 경우, 바로 앞자리 숫자는 j-1 또는 j+1

  → 계단 수를 결정하는 방식은 끝자리 숫자에 따라 달라진다.

• 인접한 자리의 숫자의 차이가 1이라는 조건

  • 각 자리 숫자가 독립적이지 않고, 이전 자리 숫자에 의존한다는 것을 유추해 낼 수 있다.
  • 따라서, 자리수(N)와 끝자리 숫자를 기준으로 상태를 구분해야 한다.

• 자리수가 N 이므로 상태는 자리별로 누적

  • dp[1][1]=1: 길이가 1이고 끝자리가 1인 경우.

• 각 자리의 끝자리 숫자에 따라 다음 자리로 확장되는 방식이 다르기 때문에 끝자리 숫자와 길이를 동시에 추적해야 한다. → 2차원 배열 도출

점화식 도출

• N자리 숫자의 끝자리가 j인 경우, 바로 앞자리 숫자는 j-1 또는 j+1

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

• j-1 > 0 이며, j+1 < 9 를 만족해야 하기 때문에 아래와 같이 표현

if (j > 0) dp[i][j] += dp[i - 1][j - 1];
if (j < 9) dp[i][j] += dp[i - 1][j + 1];

code