[ 백준 10844 ] ( python ) 쉬운 계단 수

 

📚 쉬운 계단 수

 

문제

45656이란 수를 보자.

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

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

 

입력

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

 

출력

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

 

예제 입력 1 복사

1

예제 출력 1 복사

9

예제 입력 2 복사

2

예제 출력 2 복사

17

 

 

 

✍ 접근

• 규칙찾기!
• 2차원 배열을 돌면서 0~9가 마지막 숫자로 올 수 있는 개수를 세어준다
• board를 그려서 해결하면 더 간단하다

 

 

 

 

정답코드

# ✨ 입력
import sys
input = sys.stdin.readline
N = int(input())
MOB = 1000000000

# ✨ 구분 1
dy = [[0]*10 for _ in range(N+1)]
for i in range(1,10):
    dy[1][i] = 1

# ✨ 구분 2
for i in range(2,N+1):
    for j in range(10):
        if j == 0 : 
            dy[i][j] = dy[i-1][j+1]
        elif j == 9:
            dy[i][j] = dy[i-1][j-1]
        else:
            dy[i][j] = dy[i-1][j-1] + dy[i-1][j+1]

# ✨ 출력
print(sum(dy[N])%MOB)

 

✨ 구분 1

• dy를 N+1만큼 for문으로 돌고, 내부 배열은 0~9까지 10개의 칸을 0으로 리셋해준다
• for문을 돌면서 dy[1]일 때 == 한 자리 수 일 때 마지막 숫자가 될 수 있는 숫자들에 1을 추가해준다.
• board를 보면 이해가 더 쉽다

 

✨ 구분 2

<board>

0 1 2 3 4 5 6 7 8 9 

0,1,1,1,1,1,1,1,1,1 => 1자리 숫자일 때 맨 마지막에 올 수 있는 수의 개수. 0은 올 수 없기 때문에 0이다

1,2,2,2,2,2,2,2,2,1 => 2자리 숫자일 때 맨 마지막에 올 수 있는 수의 개수,

• 예를 들어 마지막 자리가 4가 될 수 있는 경우는, 끝 자리가 3일 때와 끝 자리가 5일 때의 경우다.
• 따라서 i-1자리의 숫자일 때 끝 자리가 3일때의 경우= 1, 끝 자리가 5일 때의 경우 1 을 더해서 현재 자리 끝 자리가 4인 경우를 구한다 == 2
• 만약 끝자리가 0일 경우라면, 0은 i-1자리 끝 자리가 1일 때밖에 안되기 때문에 i-1이 1일 경우에서만 값을 가져와야 하고
• 끝자리가 9일 경우도 마찬가지로, i-1자리 끝 자리가 8일 때만 이번 끝자리가 9가 될 수 있기 때문에, i-1 8의 값을 가져와야 한다

 

 

 

 

⭐ 배움

• 직관적으로 규칙을 못찾겠으면 리스트를 그려가면서 규칙을 찾는 것이 답이다
• 조금만 더 뇌가 말랑말랑해지면 잘 풀 수 있을 것 같은 느낌..!?😖