반응형
모든 인접한 수의 차이가 1인 수의 갯수를 찾는 문제
n=1일때,
1,2,3,4,5,6,7,8,9의 9개이다. (0으로 시작은 안되므로 제외)
n=2일때,
10 21 32 12 23 43 54 34 65 45 56 76 67 87 78 98 89 90의 17개이다.
여기서 잘보면, n이 1일때의 두배에서 -1한 것임을 알 수 있다. 이게 n=3일때도 잘 작동해서 일반항이 n(k)=n(k-1)-(k-1)인지 알았으나 5부터 잘 작동하지 않았다.
그렇다면, 일반항을 따로 구할 수 없으니 케이스를 쪼개서 이전값에서 받아오자.
규칙을 찾으면, 어떤 수가 n으로 끝난다면, n으로 끝나는 수의 갯수는 이전 수의 n-1로 끝나는 수와 n+1로 끝나는 수의 갯수의 합이라는 것이다.
여기서 특이 케이스가 보이는데 바로 0과 9이다.
0과 9로 끝나는 수들은 다음 자리수에 1과 8로 끝날 수 밖에 없다. 따라서 얘네를 예외처리해준다.
import sys
input=sys.stdin.readline
n=int(input())
numcase=[[0 for _ in range(10)] for _ in range(n)]
numcase[0]=[0,1,1,1,1,1,1,1,1,1]
for x in range(1,n):
numcase[x][0]=numcase[x-1][1]
numcase[x][9]=numcase[x-1][8]
for y in range(1,9):
numcase[x][y]=numcase[x-1][y+1]+numcase[x-1][y-1]
print(sum(numcase[-1])%1000000000)반응형
