[BOJ] 오르막 수(11057) - PYTHON

숫자의 길이 N이 주어질 때 N의 길이로 만들 수 있는 오르막 수의 개수를 구하는 문제다.
오르막 수란 수에서 모든 인접한 숫자가 오름차순으로 연결되는 수를 말한다. 인접한 숫자는 같아도 된다.
N은 최대 1000이다.

ex)
1, 2, 11, 12, 123, 112는 오르막 수다.
21, 12343, 154는 오르막 수가 아니다.

시간 복잡도: O(N * 10)

11057번: 오르막 수

---

풀이 과정

모든 경우를 탐색하는 완전 탐색으로 문제를 해결하려면 오랜 시간이 걸린다. 가령 N = 1000이고 0부터 9가 1000개 이어진 수까지 탐색하며 오르막 수인 지 검사하려면 매우 오래 걸리게 된다. 완전 탐색으로 풀이 시 시간 복잡도는 O(10^N)이다.

하지만 오르막 수는 길이가 1씩 증가할 때마다 이전 길이의 오르막 수 개수와 연관성이 있다.
끝자리가 각각 0~9인 오르막 수의 개수를 저장하는 배열을 선언한다면, 오르막 수 길이가 1 증가할 때 마지막 숫자가 0~9인 오르막 수의 개수는 각각 이전 길이의 오르막 수 개수 중 끝자리가 현재 수의 끝자리 보다 작거나 같은 오르막 수 개수의 합과 같다.

예를 들어  N = 1일 때 끝자리가 0~9인 오르막 수의 개수를 나타내는 배열을 나타낸다면 그 배열은 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]이다.
이제 N = 2일 때 끝자리가 0~9인 오르막 수의 개수를 나타내는 배열을 만들면 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]이 된다.
구하는 방법은 이전 배열에서 0~해당 inedx까지의 값을 구하면 된다. 즉 dp[N][K] = sum(dp[N-1][0:K + 1])이다

---

 코드

N = int(input())
 
dp = [[0] * 10 for _ in range(N)]
for i in range(10):
    dp[0][i] = 1
for i in range(1, N):
    temp = 0
    for j in range(10):
        temp += dp[i - 1][j]
        temp %= 10007
        dp[i][j] = temp
print(sum(dp[N - 1]) % 10007)

주석 추가

N = int(input())
 
dp = [[0] * 10 for _ in range(N)]  # 길이 1~N에 대해 끝 자리가 0~9인 오르막 수의 개수를 담을 2차원 배열
for i in range(10):  # 1자리 오르막수 개수 초기화
    dp[0][i] = 1
for i in range(1, N):  # 길이가 N까지 가면서
    temp = 0  # 이전길이에서 끝자리가 0~j인 오르막 수의 개수를 저장할 변수
    for j in range(10):
        temp += dp[i - 1][j]  # 이전길이 dp배열에서 현재 끝자리 값을 더하기
        temp %= 10007
        dp[i][j] = temp  # dp값 저장
print(sum(dp[N - 1]) % 10007)  # 정답값은 길이 N인 0~9까지 오르막 수의 합 % 10007

---

채점 결과

정답 값을 산출할 때 10007로 나눈 나머지 값을 출력해야 한다는 조건을 넣지 않아 2번 틀렸다.