[BOJ] #10844. 쉬운 계단 수 (Python)

mingguriguri·2022년 10월 30일

DP python 백준 알고리즘

Python으로 공부하는 Algorithm

목록 보기

2/10

#10844. 쉬운 계단 수

링크: https://www.acmicpc.net/problem/10844
유형: 동적프로그래밍
작성일시: 2022년 10월 15일 오후 11:21
출처 : 백준 온라인 저지

✔ 문제 #10844. 쉬운 계단의 수

💡 인접한 모든 자리의 차이가 1인 계단수가 있다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구한다. 0으로 시작하지 않는다.

input : N (1≤N≤100)

output: 정답을 1,000,000,000로 나눈 나머지

input

output

✔ 풀이과정

💡 **힌트** : 구구단 코드와 비슷하다, 테이블을 사용한다. 각각의 케이스를 구분하자.(if문)

모든 경우의 수를 구하는 것이다. 근데 하나하나 다 풀려고 하면 너무 복잡해진다.

각각의 케이스를 구해보자. N이 1일 때, 자리수가 1이기 때문에 각 숫자들이 맨 뒷자리에 올 수 있는 개수는 1씩이다.

맨 뒤에 0이 올 수 있는 경우의 수 - 0으로 시작할 수 없고, 1만 올 수 있다. ⇒ (1개)
맨 뒤에 1이 올 수 있는 경우의 수 - 21가 올 수 있다. 01은 올 수 없다. ⇒(1개)
맨 뒤에 2가 올 수 있는 경우의 수 - 12, 32가 올 수 있다. ⇒(2개)
맨 뒤에 9이 올 수 있는 경우의 수 - 8만 올 수 있다. ⇒(1개)

i \ j	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	2

따라서 이를 이용해서 테이블을 만들고 해당 점화식을 세운다!

i = 자리수(N), j = 맨 뒤에 갈 수 있는 경우의 수

j = 0 → num[i][j] = num[i-1][1]

j = 9 → num[i][j] = num[i-1][8]

j = 2~8 → num[i][j] = num[i-1][j-1] + num[i-1][j]

내 풀이

n = int(input())

num = [[0]*10 for _ in range(n+1)]
num[0] = [1,1,1,1,1,1,1,1,0] #0행에 들어가는 값들을 계단수의 경우의수로 초기화

for i in range(1,n+1):
    for j in range(10): #0일때, 9일때, 나머지인 경우를 점화식을 토대로 코드 작성
        if j == 0: 
            num[i][j] = num[i-1][1]
        elif j == 9:
            num[i][j] = num[i-1][8]
        else:
            num[i][j] = num[i-1][j-1] + num[i-1][j]

answer = sum(num[n]) % 100000000
print(answer)

이 풀이는 런타임에러가 난다.

다른 풀이

n = int(input())

num = [[0]*10 for _ in range(n+1)]
num[0] = [0,1,1,1,1,1,1,1,1]

for i in range(1,n+1):
    for j in range(10):
        if j == 0:
            num[i][j] = num[i-1][j+1]
        elif j == 9:
            num[i][j] = num[i-1][j-1]
        else:
            num[i][j] = num[i-1][j-1] + num[i-1][j+1]

answer = sum(num[n]) % 100000000
print(answer)