728x90
반응형
문제:
45656이란 수를 보자.
이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다. 세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다. N이 주어질
때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)
입력:
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
출력:
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
풀이 방법:
길이가 하나 길어질수록 그 전의 길이에 영향을 받는다. 임의의 숫자 n에 대해서 생겨지는 계단 수의 수는 이전의 n-1 과 n+1의 수의 합이다. 하지만 끝값 0이나 9와 같은 경우에는 계단수를 유지하기 위해 각각 1과 8만 와야 하므로 이 경우에 대해서만 더해주도록 한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | dp=[] for i in range(int(input())+1): dp.append([]) for j in range(10): if i==1: dp[i].append(1) else: dp[i].append(0) for i in range(2,len(dp)): for j in range(10): if j==0: dp[i][j]+=dp[i-1][j+1]%1000000000 elif j==9: dp[i][j]+=dp[i-1][j-1]%1000000000 else: dp[i][j]+=dp[i-1][j-1]+dp[i-1][j+1]%1000000000 print(sum(dp[-1][1:])%1000000000) | cs |
728x90
반응형
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]9095. 1,2,3 더하기 (0) | 2019.04.24 |
|---|---|
| [BOJ]11052. 카드 구매하기 (0) | 2019.04.23 |
| [BOJ]1149. RGB거리 (0) | 2019.04.21 |
| [BOJ]2163. 초콜릿 자르기 (0) | 2019.04.20 |
| [BOJ]1912. 연속합 (0) | 2019.04.19 |