출처 : 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 일 때는 알고 있으니 순서대로 더해준다.
'알고리즘 문제 풀이' 카테고리의 다른 글
백준 11057 : 오르막 수 (Python) (1) | 2022.12.31 |
---|---|
백준 15649, 15650 : N과 M (1), (2) (Python) (0) | 2022.12.26 |
백준 1463번 : 1로 만들기 (Python) (0) | 2022.12.15 |
백준 2468번 : 안전영역 (Python) (0) | 2022.12.12 |
백준 1083번 : 소트 (Python) (0) | 2022.12.07 |
댓글