백준 - 계단 수(1562)
Dynamic Programming
문제
45656이란 수를 보자.
이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.
그럼, 오늘도 역시 세준이는 0부터 9까지 모든 한 자리수가 자리수로 등장하면서, 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.
N이 주어질 때, 길이가 N이면서 0에서 9가 모두 등장하는 계단 수가 총 몇 개 있는 지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)
입력
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
힌트
참고로, N = 1일때부터, N = 40일 때 까지 답을 모두 더하면 126461847755이 나온다.
n = int(input())
re = 0
dp = [[0 for _ in range(1024)] for _ in range(10)]
for i in range(1, 10):
dp[i][1<<i] = 1
for i in range(1, n):
dp_next = [[0 for _ in range(1024)] for _ in range(10)]
for e in range(10):
for bm in range(1024):
if e < 9:
dp_next[e][bm | (1<<e)] = (dp_next[e][bm | (1<<e)] + dp[e+1][bm]) % 1000000000
if e > 0:
dp_next[e][bm | (1<<e)] = (dp_next[e][bm | (1<<e)] + dp[e-1][bm]) % 1000000000
dp = dp_next
print(sum([dp[i][1023] for i in range(10)]) % 1000000000)
상당한 난이도..
참고)
https://m.blog.naver.com/PostView.nhn?blogId=occidere&logNo=221130521559&proxyReferer=https:%2F%2Fwww.google.com%2F
https://hddcp.tistory.com/18
Author And Source
이 문제에 관하여(백준 - 계단 수(1562)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@skkfea07/백준-계단-수1562저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)