[Python/파이썬] 백준 알고리즘 10844 - 쉬운 계단 수 (DP)

 

 

 

<풀이>

처음에는 백트래킹으로 풀 생각을 했다..

import sys
sys.setrecursionlimit(10 ** 6)

input = sys.stdin.readline

N = int(input())
cnt = 0

def backTracking(depth):
    if depth == N:
        global cnt
        cnt += 1
        return
    elif num[-1] == 0:
        num.append(1)
        backTracking(depth + 1)
        num.pop()
    elif num[-1] == 9:
        num.append(8)
        backTracking(depth + 1)
        num.pop()
    else:
        for i in (num[-1] - 1, num[-1] + 1):
            num.append(i)
            backTracking(depth + 1)
            num.pop()


for i in range(1, 10):
    num = [i]
    backTracking(1)

print(cnt)

하지만 시간초과가 떴다..

 

그래서 BFS로 다시 풀어보았다.

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
cnt = 0

queue = deque()
for i in range(1, 10):
    queue.clear()
    queue.append([i, 1])
    while queue:
        popNum, length = queue.popleft()
        if length == N:
            cnt += 1
        if length > N:
            break
        for newNum in (popNum-1, popNum+1):
            if 0<=newNum<10:
                queue.append([newNum, length+1])

print(cnt)

하지만 이것도 시간초과가 떴다..

 

그래서 구글링을 해보니 DP로 풀 수 있는 문제였다.

 

DP로 풀기위해선 점화식을 찾아야한다.

예시를 들며 찾아보겠다.

 

예를들어 자리수가 2일때를 생각해 보면,

1. 맨 뒤에 0이 올 수 있는 경우 : 10 (1개)

2. 맨 뒤에 1이 올 수 있는 경우 : 21 (1개)

3. 맨 뒤에 2가 올 수 있는 경우 : 12, 32 (2개)

이다. 이를 표로 작성해보면 아래와 같다.

 

                0  1  2  3  4  5  6  7  8  9
자리수(1)   0  1  1  1  1  1  1  1  1  1
자리수(2)   1  1  2  2  2  2  2  2  2  1
자리수(3)   1  3  3  4  4  4  4  4  3  2

 

위 숫자들은 각 자리수에서 해당 숫자가 나올 수 있는 가지수를 의미한다.

 

보면 한 자리의 값은 양쪽 대각선 위 위치 숫자들의 합이다.

이것은 당연하다 왜냐하면 예를들어 2가 뒤에 나오려면 앞서 1이나 3이 나와야 하기 때문이다.

 

이를 바탕으로 점화식을 생각하면 아래와 같다.

j = 0          dp[i][j] = dp[i - 1][j + 1]

j = 9          dp[i][j] = dp[i - 1][j - 1]

j = 2 ~ 8    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]

(i는 자리수, j는 맨 뒤에 위치하는 숫자)

 

성공한 코드는 아래와 같다.

import sys

input = sys.stdin.readline

N = int(input())
dp = [[0] * 10 for _ in range(N+1)]

for i in range(1, 10):
    dp[1][i] = 1
for i in range(2, N+1):
    for j in range(10):
        if j == 0:
            dp[i][j] = dp[i-1][j+1]
        elif j == 9:
            dp[i][j] = dp[i-1][j-1]
        else:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
print(sum(dp[N]) % 1000000000)

 

 

 

<핵심 정리>

1. 시간복잡도를 계산해보고 BFS, DFS가 아닌거 같을땐 DP를 의심해보자.

2. DP는 결국 점화식을 찾아내는게 일이다. 어떻게해서든 찾아내보자