KOREATECH 1057: 걸기 쉬운 전화번호

Link : judge.koreatech.ac.kr/problem.php?id=1057

---

Python

from sys import stdin
 
num = dict()
num[1] = [2, 4]
num[2] = [1, 3, 5]
num[3] = [2, 6]
num[4] = [1, 5, 7]
num[5] = [2, 4, 6, 8]
num[6] = [3, 5, 9]
num[7] = [4, 8]
num[8] = [5, 7, 9, 0]
num[9] = [6, 8]
num[0] = [8]
 
dp = [[0 for _ in range(101)] for _ in range(10)]
 
 
def solve(number, length):
    if length == 1:
        return 1
 
    if dp[number][length] != 0:
        return dp[number][length]
 
    result = 0
    for data in num[number]:
        result += solve(data, length - 1)
        result %= 1000000007
 
    dp[number][length] = result
    return result
 
 
test = int(stdin.readline().strip())
for i in range(test):
    n = int(stdin.readline().strip())
    result = 0
    for i in range(10):
        result += solve(i, n)
        result %= 1000000007
 
    print(result)

FeedBack

1.  

---

 

 

 

cjw.git@gmail.com