[다이나믹 프로그래밍] 10844번 - 쉬운 계단 수

[백준] 10844번 - 쉬운 계단 수

(한줄평) 생각보다 빨리 아이디어가 떠올라 쉽게 풀 수 있었던 문제! 2차원으로 접근해야한다는 것을 깨달으면 쉽게 풀 수 있다. 한번쯤 복습해보면 좋을 것 같은 문제

 

풀이 시간: 20분 이내

1) 문제 해결 아이디어

인접한 모든 자리의 차이가 1인 수를 계단수라고 한다. (단, 0으로 시작하는 수는 계단수가 아니다)

1이상 100이하의 자연수 n이 주어질 때, 길이가 n인 계단 수의 총 개수를 구하는 문제다.

 

길이가 n인 계단 수의 마지막 숫자는 0 ~ 9 사이의 수로 10가지 경우가 있다.

길이가 n, 마지막 숫자가 j인 계단 수의 개수 = 길이가 (n - 1)인 계단수 중 j - 1, j + 1 로 끝나는 계단수의 개수의 합이다.

그러므로 길이가 n인 계단수의 총 개수 = 길이가 n인 (0 ~ 9)로 끝나는 계단 수의 개수의 합과 같다.

 

첫번째 오류. 틀렸습니다

출력값을 10**9으로 나눈 나머지를 출력해야하는데 그냥 값을 출력해서 바로 틀렸습니다가 나왔다.

 

<점화식>

0은 인접한 숫자가 1 1개이고 9는 인접한 숫자가 8 1개이다.

나머지 숫자는 현재 숫자 - 1, 현재 숫자 + 1 한 값 2개이다.

이렇게 예외 처리를 하지 않으면 IndexError가 난다.

 

 

2) 소스코드

n = int(input())  # 1이상 100이하 자연수
d = [[0] * 10 for _ in range(n)]
d[0] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

for i in range(1, n):
  for j in range(10):
    if j == 0:  d[i][j] = (d[i - 1][j + 1])
    elif j == 9:  d[i][j] = d[i - 1][j - 1]
    else:
      d[i][j] = d[i - 1][j - 1] + d[i - 1][j + 1]

print(sum(d[n - 1]) % 10**9)