백준 10844번 파이썬 문제풀이(DP - 쉬운 계단 수)

---

해당 문제는 다음과 같은 방법으로 접근할 수 있어야 한다.

1. dp를 이차원 배열로 설정한다.

2. 이차원 배열중 행은 N(자리수) 열은 맨뒷자리에 오는수(10이라면0 231이라면 1) 라고 생각을 해야한다 (dp[자리수][맨뒤에오는수]) 

3. 맨 앞자리가 0일때는 횟수를 세지 않는다.

4. 1~8일때는 전에 자리수에서 -1,+1 일때의 횟수를 더해주면된다. (ex) 2일때는 1일때와 3일때의 횟수에서 두개를 더해준값이다. 왜냐하면 12 or 32 으로 맨뒤에 2가 올 수 있는 경우의 수이기 때문이다.

5. 9일때는 8밖에 올 수 없다. 즉, 89xxx... 밖에 될 수 없기 때문이다.

정리하자면 

N=1일때 dp[1][0] = 0 , dp[1][1] ~ dp[1][9] = 1

N=2일때 dp[2][0] = 0 , dp[2][1] ~ dp[2][8] = 2 ,  dp[2][9] = 1

와 같이 채워져야 한다. 

 

점화식으로 풀면

dp[N][0] = 0

dp[N][1] ~ dp[N-1][8] = dp[N-1][i-1]+dp[N-1][i+1] <- 여기서 i는 1~8

dp[N][9] = dp[N-1][8]

 

N = int(input())

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

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

MOD = 1000000000

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

print(sum(dp[N]) % MOD)

 

출처:https://cotak.tistory.com/12

[백준] 10844 - 쉬운 계단 수 [Python(파이썬)]