[백준 10844번] 쉬운 계단 수 in python

문제

45656이란 수를 보자.

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

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

입력

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

출력

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

 

예제 입력 1 

1

예제 출력 1 

9

예제 입력 2 

2

예제 출력 2 

17

 

---

문제에 대한 설명이 부족했으나, 대충 이해는 했다.

1일 때, 계단 수는 1,2,3,4,5,6,7,8,9 총 9개이다.

2일 때, 계단 수는 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98 총 17가지가 있다.

 

즉 뒷자리가 0일 때 또는 9일 때 다음에 늘어날 수는 1개. 나머지는 2개로 이해했다.

이렇게 코드를 작성해보았다.

N=int(input())
num_lst=list(range(1,10))



for n in range(1,N):
  temp_num_lst=[]
  for num in num_lst:
    if num%(10**n)==0:
      temp_num_lst.append(int(str(num)+'1'))
    elif num%(10**n)==9:
      temp_num_lst.append(int(str(num)+'8'))
    else :
      i=num%(10**n)
      temp_num_lst.append(int(str(num)+str(i-1)))
      temp_num_lst.append(int(str(num)+str(i+1)))
  num_lst=temp_num_lst

print(len(num_lst))

 그러나.. 시간초과가 나고 또 틀렸다 ㅜㅜ

 

 

이 방식으로 접근하기 보다 

            :   0 1 2 3 4 5 6 7 8 9

1의 자리 :   0 1 1 1 1 1 1 1 1 1

2의 자리 :   1 1 2 2 2 2 2 2 2 1

3의 자리 :   1 3 3 4 4 4 4 4 3 3

 

이렇게 대각선으로만 합쳐진다는 것을 알게 되었다. 0과 9는 왼쪽 대각선과 오른쪽 대각선이 없으니 남은 대각선만 그대로 옮겨주면 된다.

이런 공식이 있었다ㅜㅜ 어떻게 찾을까...

여튼 이 방법대로 진행해서 코드를 짜봤다.

N=int(input())

num_lst=[0,1,1,1,1,1,1,1,1,1]

for n in range(1,N):
  temp=[]
  for idx in range(len(num_lst)):
    if idx==0:
      temp.append(num_lst[1])
    elif idx==9:
      temp.append(num_lst[8])
    else:
      temp.append(num_lst[idx-1]+num_lst[idx+1])
  num_lst=temp
print(sum(num_lst)%1000000000)

임시로 temp 리스트를 만들어서 num_lst로 바꾸는 방법으로 진행했다.