[백준] 10884번 (python 파이썬)

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

10844번: 쉬운 계단 수

계단 수(n) 은 계단 수(n-1) 와 계단 수(n-1)의 끝자리인 수 ± 1 가 이어진 수

 

예를 들어

1234 = 123 와 123의 끝자리인 3 + 1 이 이어진 수

1232 = 123 와 123의 끝자리인 3 - 1 이 이어진 수

 

즉, 계단 수(n)의 끝자리 수는 계단 수(n-1)의 끝자리 수의 +1인 수이거나 -1인 수이다.

 

이를 통해 다음과 같은 규칙을 찾을 수 있다.

 

num = int(input())

cache = [[0 for _ in range(10)] for _ in range(num+1)]

cache[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

for n in range(2, num+1):
  cache[n][0] = cache[n-1][1]
  for i in range(1,9):
    cache[n][i] = cache[n-1][i-1] + cache[n-1][i+1]
  cache[n][9] = cache[n-1][8]
print(sum(cache[num]) % 1000000000)

 

또한 모듈러 연산이 나왔다.

이 문제는 위의 코드로 실행해도 시간초과가 나오지 않는다.

하지만 모듈러 연산을 통해서 값이 기하급수로 커지는 걸 방지할 수 있다.

 

num = int(input())

cache = [[0 for _ in range(10)] for _ in range(num+1)]

cache[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

for n in range(2, num+1):
  cache[n][0] = cache[n-1][1] % 1000000000
  for i in range(1,9):
    cache[n][i] = (cache[n-1][i-1] % 1000000000 + cache[n-1][i+1] % 1000000000) % 1000000000
  cache[n][9] = cache[n-1][8] % 1000000000
print(sum(cache[num]) % 1000000000)