백준 10844번 파이썬 - 쉬운 계단 수

 

10844번: 쉬운 계단 수

최근 DP 문제를 풀기 시작했고, 점화식 찾는데 익숙하지 않아서 1시간 이상 붙잡다가 매번 문제풀이를 봤다.. 문제는  풀 때 최대 1시간 ~ 1시간 반까지만 생각하고 풀이가 떠오르지 않으면 문제 풀이를 찾아보는 식으로 스스로 정했다.

이번에는 꼭 뭔가 풀 수 있을 것 같다는 생각이 들어 1시간 반 가까이 생각해서 이전에 풀었던 문제풀이를 활용해서 문제를 풀 수 있었다.

2차원 배열을 이용하는 것이다.

d[i][j] : 자리수가 i(1개 ~ 100개) 개인 수에서 마지막 자리수가 j ( 0 ~ 9까지) 로 끝나는 계단 수가 총 몇 개인지 의미.
 즉 d[i] 는 자리수가 i 개인 숫자들 중에서 계단 수가 몇 개인지 나타낸다.
d[i][j] = d[i - 1][j + 1] + d[i - 1][j - 1]
d[i][j]는 자리수가 1 작은 수들 중, 자리수 차이가 1이 나는 끝자리 수(+1,-1)들의 합과 같다. d[2][3] => 자리수가 1개인 수 중에서 끝자리가 2 또는 4에서 파생된다. ex) 2 와 4 => 23, 43

코드

max = 101
d = [[0] * 10 for _ in range(max)]

n = int(input())
d[1] = [0,1,1,1,1,1,1,1,1,1]
a = 1000000000

# d[i][j]는 i자리수에서 j라는 수로 끝나는 수의 개수를 의미.
# 끝자리가 0과 9일 때는 자리수 차이가 1이 가능한 것이 0은 앞자리가 1일때, 9는 앞자리가 8일때만 가능해서
# if 문으로 경우를 따로 나눈다.
for i in range(2, max):
    for j in range(10):
        if j != 0 and j != 9:
            d[i][j] = d[i - 1][j + 1] + d[i - 1][j - 1]
        else:
            if j == 0:# 0으로 끝나는 자리 수 일때
                d[i][j] = d[i - 1][j + 1]
            else:# 9로 끝나는 자리 수 일 때
                d[i][j] = d[i - 1][j - 1]
        d[i][j] %= a
print(sum(d[n]) % a)