[10844] 쉬운 계단 수

문제

백준 문제

45656이란 수를 보자.

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

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 1 

1

예제 출력 1 

9

예제 입력 2 

2

예제 출력 2 

17

---

풀이

MOD = 1_000_000_000

# 입력 받기
n = int(input())

# DP 테이블 초기화 (n+1 길이로 생성)
dp = [[0] * 10 for _ in range(n + 1)]  # 10이 오는 이유: 각 숫자의 끝자리(0~9)에 대한 계단 수 개수 저장

# 길이가 1일 때, 1~9까지 계단 수는 각 1개
for i in range(1, 10):
    dp[1][i] = 1    # dp[i][j]: 길이가 i이고, 끝자리가 j인 계단 수의 개수

# DP 진행 (점화식 적용)
for i in range(2, n + 1):
    for j in range(10):
        # 끝자리가 0이면 이전에서 1만 가능
        if j == 0:
            dp[i][j] = dp[i - 1][1]
        # 끝자리가 9이면 이전에서 8만 가능
        elif j == 9:
            dp[i][j] = dp[i - 1][8]
        # 그 외에는 이전에서 ±1 가능
        else:
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]
        
        # 값이 너무 커지지 않도록 MOD 연산 적용
        dp[i][j] %= MOD

# 길이가 n인 모든 계단 수의 합 구하기
result = sum(dp[n]) % MOD
print(result)

 

 

 

• DP 테이블에서 10을 사용하는 이유?
  → 끝자리 숫자(0~9)를 저장하기 위해서
• 길이는 무엇을 의미하나?
  → 숫자의 자릿수를 의미
• dp[i][j]는 무엇을 의미하나?
  → 길이가 i이고 끝자리가 j인 계단 수의 개수.
• 초기값을 왜 그렇게 설정하나?
  → 길이가 1일 때는 각 숫자(1~9)가 하나씩 계단 수로 존재하기 때문
• 왜 10, 12, 21로 가고 14로 안 가나?
  → 계단 수는 인접한 자리의 차이가 반드시 1이어야 하기 때문

 

---