BOJ 1088 쉬운 계단 수 python3

문제 : https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

코드

from sys import stdin
input = stdin.readline

NANUGE = 1000000000
N = int(input())

# 격자 틀 만들기
dp = [[-1 for _ in range(10)] for _ in range(N+1)]
dp[1] = [1 for _ in range(10)]

# 격자 채우기
for i in range(2, N+1):
    for start_number in range(10):
        if start_number == 0: # 길이가 i, 0으로 시작하는 숫자
            dp[i][start_number] = dp[i-1][start_number+1]
        elif start_number == 9: # 길이가 i, 9로 시작하는 숫자
            dp[i][start_number] = dp[i-1][start_number-1]
        else: # 길이가 i인 숫자
            dp[i][start_number] = dp[i-1][start_number-1] + dp[i-1][start_number+1]


# 0으로 시작하는 숫자는 제외하고 출력
print(sum(dp[N][1:]) % NANUGE)

 

해설

규칙은 어렴풋이 알겠는데 생각을 잘못해서 삽질한 문제이다. 

그림 1. 삽질하면서 그린 표

원래는 저렇게 계단수를 늘어놓고, 그 수의 가장 마지막 자리 뒤에 올 수 있는 가짓수를 세려고 했다. (ex: 3 뒤에는 2와 4가 올 수 있으므로, 123 뒤에는 2와 4가 올 수 있다.)

그러나 그렇게 하면 너무 많은 수를 저장해야 하기에 딱봐도 메모리가 터질 것 같았다.

 

그림 2. N과 시작 숫자에 따른 가능한 계단수의 개수

표를 이렇게 그리면 규칙을 간단히 찾을 수 있다.

• x축 : 숫자의 길이
• y축 : 시작 숫자
• cell : 가능한 계단수의 개수

예를 들어, dp[2][1]은 숫자의 길이가 2이고 1로 시작하는 계단수의 개수이다. (10, 12)

위 표를 살펴보면, 각 셀은 좌우 대각선의 합임을 알 수 있다. 즉, 다음과 같이 나타낼 수 있다.

 

그림 3. 일반식

따라서 위 식을 따라 dp 배열을 채워주면 된다.