풀이_10844.md

🪝 백준 10844번 (쉬운 계단 수)

• Date : 2021.03.22(토)
• Time : 30분

문제

• 45656이란 수를 보자. 이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다. 세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력

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

출력

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

풀이

candi_list = [[0 for i in range(10)] for j in range(N+1)]

for i in range(1, 10):
    candi_list[1][i] = 1

for i in range(2, N + 1):
    for j in range(10):
        if j == 0:
            candi_list[i][j] = candi_list[i - 1][1]
        elif j == 9:
            candi_list[i][j] = candi_list[i - 1][8]
        else:
            candi_list[i][j] = candi_list[i - 1][j - 1] + candi_list[i - 1][j + 1]

: 각 자리수에서 맨 뒤에 올 수 있는 개수를 배열로 구하는 방법이다. 먼저 N=1 일때는 1자리수이기 때문에 맨 뒤에 올 수 있는 개수는 1개이다. 만약 자리수가 2(N=2)일때는 맨 뒤에 0이 오는 경우는 1개(10), 맨 뒤에 2가 오는 경우는 2개(32,12) 처럼 대각선의 숫자가 위치하는 규칙을 알 수 있다. 이 규칙으로 if문을 세워주었다.