[백준 BOJ_10844] 쉬운 계단 수 Python 풀이

출처: 백준 온라인 저지

문제

풀이

동적계획법으로 풀어 보겠습니다.

cache의 format은 다음과 같습니다.

# cache[N 자릿수][끝나는 수]
cache[1 ~ N][0 ~ 9]: 0 ~ 9로 끝나는 N 자릿수의 개수

한 자릿수(cache[1])는 1부터 9로 끝나는 숫자가 1부터 9까지 1개씩이므로 1로 초기화해줍니다.

• 0으로 끝나는 한 자릿수(cache[1][0])는 0 하나이지만, 한 자릿수라서 끝나는 수가 시작하는 수가 됩니다. 미리 언급한 것처럼 0으로 시작하는 수는 없기에 0으로 끝나는 한 자릿수(cache[1][0])는 0이 됩니다.

outer for loop을 2부터 N+1까지 돌려줍니다. (i)

• cache[i][0] = cache[i-1][1]
• cache[i][9] = cache[i-1][8]
  • 0과 9는 차이가 1이 나는 숫자가 각각 1과 8밖에 없으므로 각각 1과 8로 끝나는 i-1 자릿수의 개수로 저장해줍니다. inner for loop을 1부터 9까지 돌려줍니다.
• cache[i][j] = cache[i-1][j-1] + cache[i-1][j+1]
  • j로 끝나는 i 자릿수의 개수(cache[i][j])는 j보다 1이 작은 수로 끝나는 i-1 자릿수의 개수(cache[i-1][j-1])와 j보다 1이 큰 수로 끝나는 i-1 자릿수의 개수(cache[i-1][j+1])를 합한 수를 저장해줍니다.

마지막으로 N 자릿수(cache[N])의 개수를 모두 더한 값에 1000000000으로 나눈 나머지를 출력해줍니다.

코드

N = int(input())
cache = [[0 for _ in range(10)] for _ in range(N+1)]
cache[1] = [1 for _ in range(10)]
cache[1][0] = 0 
for i in range(2, N+1):
    cache[i][0] = cache[i-1][1]
    cache[i][9] = cache[i-1][8]
    for j in range(1,9):
        cache[i][j] = cache[i-1][j-1] + cache[i-1][j+1]
print(sum(cache[N])%1000000000)