[백준] 2780. 비밀번호 - Python

[Silver I]

 

https://www.acmicpc.net/problem/2780

2780번: 비밀번호

 

풀이

간단한 DP 문제.

 

비밀번호 길이가 i일 때, j라는 숫자에서 출발했을 때의 비밀번호 개수를 dp[i][j] 라 하자.

인접한 번호로만 갈 수 있으므로,

dp[i][j] 는 인접한 숫자들의 dp[i-1][~] 들의 합으로 구할 수 있다.

 

점화식은 대충 표현하자면 아래와 같다.

# dp[i][j] = dp[i-1][(인접한 숫자)] 들의 합
# ex) dp[3][2] = dp[2][1] + dp[2][3] + dp[2][5]

 

마지막에 sum 해준 답에도 MOD 연산을 수행해줘야 하는 것을 주의할 것. 필자는 이것으로 고통받았다.

AC.

T = int(input())

MOD = 1234567
# 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 순서
# dp[i][j] => 비밀번호 길이가 i일 때, j에서부터 출발하여 만들 수 있는 비밀번호의 개수.
dp = [[0],[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
out = {
    0: [7],
    1: [2, 4],
    2: [1, 3, 5],
    3: [2, 6],
    4: [1, 5, 7],
    5: [2, 4, 6, 8],
    6: [3, 5, 9],
    7: [4, 8, 0],
    8: [5, 7, 9],
    9: [6, 8],
}

for i in range(2, 1001):
    tempList = []
    # dp[i][j] = dp[i-1][(인접한 숫자)] 들의 합
    # ex) dp[3][2] = dp[2][1] + dp[2][3] + dp[2][5]
    for s in range(10):
        tempSum = 0
        for e in out[s]:
            tempSum += dp[i-1][e]
        tempList.append(tempSum % MOD)
    dp.append(tempList)
    
for _ in range(T):
    print(sum(dp[int(input())]) % MOD)