[백준11057/실버1] 오르막 수 - Python

https://www.acmicpc.net/problem/11057

 

첨엔 문제가 이해 안됐다.

수의 길이 N은 N자리수 수 중에 오르막 수를 구하라는 뜻이었다.

 

그래서 dp 배열을 10 * (N+1) 칸으로 만들었다.

그리고 dp[i][j] = i 자리 수 중에 첫번째 숫자가 j인 수의 오르막 수로 지정해서 풀었다.

 

1. 

한자리 수 중에 첫자리가 0인 수의 오르막 수 = 0개

한자리 수 중에 첫자리가 1인 수의 오르막 수 = 1개

한자리 수 중에 첫자리가 2인 수의 오르막 수 = 1개

...

한자리 수 중에 첫자리가 9인 수의 오르막 수 = 1개

이므로 dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] 로 초기화했다.

 

2. 

두자리 수 중에 첫자리가 1인 수의 오르막 수 = 한자리 수 중에 첫자리가 1~9로 시작하는 오르막수

두자리 수 중에 첫자리가 2인 수의 오르막 수 = 한자리 수 중에 첫자리가 2~9로 시작하는 오르막수

두자리 수 중에 첫자리가 3인 수의 오르막 수 = 한자리 수 중에 첫자리가 3~9로 시작하는 오르막수

...

두자리 수 중에 첫자리가 1인 수의 오르막 수 = 한자리 수 중에 첫자리가 1~9로 시작하는 오르막수

이므로

for i in range(2, N+1):
    for j in range(10):
        dp[i][j] = (sum(dp[i-1][j:])) % 10007

이렇게 dp 배열을 순회했다.

 

 

# 성공 코드 1

N = int(input())

dp = [[0] * 10 for _ in range(N+1)] # dp[i][j] : i자리수에서 첫 숫자가 j인 오르막 개수

dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

for i in range(2, N+1):
    for j in range(10):
        dp[i][j] = (sum(dp[i-1][j:])) % 10007

print((sum(dp[N]) + 1) % 10007)

 

위의 코드도 for문 안에서만 % 10007 해주고

최종 결과 출력에는 print(sum(dp[N]) + 1) 이렇게 10007로 안나눠줘서 엄청 틀렸다.

 

근데 코드가 보다보니까 dp[i][j] = dp[i-1][j] + dp[i][j-1] 로 이루어져서 누적합으로 변경할 수 있을 거같아서 리팩토링했다.

 

# 성공 코드 2

N = int(input())

dp = [[0] * 10 for _ in range(N+1)] # dp[i][j] : i자리수에서 첫 숫자가 j인 오르막 개수

dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

for i in range(2, N+1):

    # 누적합으로 변경
    dp[i][9] = dp[i-1][9]
    for j in range(8, -1, -1):
        dp[i][j] = (dp[i-1][j] + dp[i][j+1]) % 10007

print((sum(dp[N]) + 1) % 10007)