백준 10844번: 쉬운 계단 수 (파이썬)

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

10844번: 쉬운 계단 수

 

문제

 

45656이란 수를 보자.

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

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

 

입력

 

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

 

출력

 

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

 

풀이

 

문제를 읽고 DP로 해결해야 하는 문제라고 생각했다.

dp 리스트는 이차원 리스트로, 첫 번째 인덱스는 계단 수의 길이를 의미하며 두 번째 인덱스는 일의 자리가 해당 인덱스로 끝나는 계단 수의 개수를 저장하는 리스트다. 예를 들어 dp[2][3]은 길이가 2+1=3이고 일의 자리가 3으로 끝나는 123, 143와 같은 계단 수의 개수를 저장한다는 뜻이다.dp 리스트를 초기화하기 위해 가장 먼저 한 자리 계단 수를 생각해 보자. 0으로 시작하는 수는 계단 수가 아니므로 0을 제외하고, 나머지 수는 모두 계단 수다. 즉, dp[0] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]이다.다음으로 두 자리 계단 수를 생각해 보자. 일의 자리가 1로 끝나는 두 자리 계단 수는 21만 존재한다. 일의 자리가 2로 끝나는 두 자리 계단 수는 12와 32가 존재한다. 일의 자리가 3으로 끝나는 두 자리 계단 수는 23과 43이 존재한다. 일의 자리가 9로 끝나는 두 자리 계단 수는 89만 존재한다. 여기서 규칙을 찾을 수 있다. 일의 자리가 1과 9가 아닐 때는 십의 자리에 자신보다 1 작은 값과 큰 값이 올 수 있고, 일의 자리가 1과 9일 때는 십의 자리에 각각 자신보다 1 큰 값과 1 작은 값만 올 수 있다. 이를 코드로 구현할 때는 dp 리스트에 [0]*10 리스트를 추가하여 조건을 나눠 경우의 수를 직접 더하는 방식으로 문제를 해결하였다.

 

소스 코드

n = int(input())

dp = [[0, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
for i in range(n-1):
  dp.append([0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
  for j in range(10):
    if j != 0:
      dp[i+1][j-1] += dp[i][j]
    if j != 9:
      dp[i+1][j+1] += dp[i][j]
print(sum(dp[n-1])%1000000000)