10844 쉬운 계단수 파이썬

계단수의 정의

인접한 "모든" 자리의 차이가 1인수를 계단수라고함

456456은 계단수이다

 

여기서 문제는 N이  주어질때 길이가 N인 계단 수가 총 몇개있는지 구하는것이다

맨앞의 수가 0일때는 포함시키지않는다

 

즉 N은 숫자의 길이고 거기안에 계단수는 몇개가 들어가있느냐를 묻는것같다

 

글을썻는데 저장을 못해서 다 날아갔다 

앞에수가 0부터 9까지일때

0이나 9일때는 뒤의 숫자가 하나만 올수있고

나머지는 각각 두개씩 붙을수있다

 

N=1일때 

0 1 2 3 4 5 6 7 8 9

맨앞이 0일경우 제외 최종계단수 9

N=2 일때
10, 12

21, 23

32, 34

43, 45

54, 56

65, 67

76, 78

87, 89

98

n=3

101

121 123

210 212

232 234

321 323

343 345

432 434

543 545

565 567

654 656

676 678

767 765

789 787

878 876

987 989

898

즉 시작자리가 0또는 9일때는그대로

나머지는 2배가된다

거기다가 시작이 0일경우를 제외해준다

 

시작 0또는9: 1개

나머지: 8개

 

 

계단수

8*2 + 2 -1 = 17

 

N=3일떄

시작 0또는9: 2개

나머지: 15개

 

 

계단수

15*2 + 2  = 32

 

9또는 0으로 끝나는경우만 알면된다

0으로 끝나는 경우

N=2일때

10

N=3일때

210

N=4일때

1210, 3210

N=5일때

21210, 23210, 43210

6

121210, 321210, 123210, 323210, 343210, 543210

7

2121210, 2321210, 4321210, 2123210, 2323210, 4323210, 2343210, 4343210, 4543210, 6543210

 

 

9로 끝나는경우

N=1일때 

9 

1

N=2일때 

89

0

N=3일때

789, 989

1

N=4일때

6789, 8789, 8989

0

N=5일때

56789, 76789, 78789, 98789, 78989, 98989

2

N=6일때

456789, 656789, 676789, 876789, 678789, 878789, 898789, 878989, 678989, 898989

0

N=7일때 

5

 

시작자리가 9인것들만 표시해두었다

 

규칙성을 찾지 못했다

n=1

일반숫자 8 

특수숫자 1

n=2

일반숫자 15

특수숫자 2

 

아무리해도 명쾌한 규칙성은 찾기힘들었다 머리가 너무아파서 롤몇판하고 다시 문제도전

몇분지나지않아 좋은생각이났다

 

길이가 10인 리스트를 만드는것이다 각각의 인덱스는 어떤숫자의 끝자리 숫자를 의미하고

인덱스안의 요소 수는 만들수있는 총 숫자의 개수를 의미한다

N=1 [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

N=2 [1, 1, 2, 2, 2, 2, 2, 2, 2, 1]

N=3 [1, 3, 3, 4, 4, 4, 4, 4, 3, 2]

0과 9를 제외한 모든수들은 양옆의 수로 두개로 갈라져서 더해준다 그리고 N의 값은 저 리스트속 수를 모두 합한것과 같다

 

구현해보았다

N=int(input())
d=[[0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1]]
for i in range(N-1):
    d.append([0,0,0,0,0,0,0,0,0,0])
for i in range(2,N+1):
    d[i][0]=d[i-1][1]
    for j in range(1,9):
        d[i][j]=d[i-1][j-1]+d[i-1][j+1]
    d[i][9]=d[i-1][8]
print(sum(d[N])%1000000000)

제출해보니 맞았다 

0과 9끝자리에서는 다음에 하나의 수밖에 오지못한다는 사실은 빨리파악했지만 

전체숫자로 보았을때 규칙성을 파악하고 수학적으로 풀려고 시도했고 결국 규칙을 찾지 못했다

프로그래밍적으로 접근했다면 훨씬 빠른시간안에 풀수있었을것같다