본문 바로가기
알고리즘 문제 풀이

백준 10844번 : 쉬운 계단 수 (Python)

by 로널드 피셔 2022. 12. 16.

출처 : https://www.acmicpc.net/problem/10844

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

for i in range(2, n+1) :
    sols[i][0] = sols[i-1][1]
    sols[i][9] = sols[i-1][8]
    for j in range(1, 9) :
        sols[i][j] = sols[i-1][j-1] + sols[i-1][j+1]
        
print(sum(sols[-1]) % 1000000000)

k가 길이 n인 계단수일 때,

1의 자리가 0인 k의 개수는 1의 자리가 1인 길이 (n-1)인 계단수의 개수와 같다.

마찬가지로, 1의 자리가 9인 k의 개수는 1의 자리가 8인 길이 (n-1)인 계단수의 개수와 같다.

 

2 이상 8 이하의 j에 대해,

1의 자리가 j인 k의 개수는 1의 자리가 (j-1) 이거나 (j+1)인 길이 (n-1)인 계단수의 개수와 같다.

 

입력 받은 n에 대해 열의 개수가 10, 행의 개수가 (n+1)인 2차원 리스트 sols를 생성한다.

sols[i][j]는 1의 자리가 j인 길이 i인 계단수의 개수이다.

i = 1 일 때는 알고 있으니 순서대로 더해준다.

댓글