[백준] 11057번: 오르막 수

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

initial

I figured it is a math/dp question where it builds upon the previous cases. For example, n=3 will build upon n=2 numbers. But there is an easier solution below where we deduce pattern by the ending numbers.

solution

n = int(input())
dp = [[0 for _ in range(10)] for _ in range(1001)]

if n == 1:
    print(10)
    exit()
if n == 2:
    print(55)
    exit()

for i in range(10):
    dp[2][i] = 10 - i

for i in range(3, n + 1):
    for j in range(10):
        if j == 0:
            dp[i][j] = sum(dp[i - 1])
        else:
            dp[i][j] = dp[i][j-1] - dp[i - 1][j - 1]
print(sum(dp[n])%10007)

easier solution

https://jainn.tistory.com/91

We try and deduce the pattern from the back (ending number), rather than my way of doing it front way. We can see that numbers ending with 0 is 1 but else, we have the pattern of dp[j] += dp[j-1]

complexity

10*n so n time and n space? yep

The code calculates the number of n-digit numbers with the property that no two consecutive digits are the same, where the last digit can be any digit (0-9). The code uses dynamic programming to achieve this and calculates the result modulo 10007. Here's the time and space complexity:

Time Complexity:

• The code uses a nested loop structure, iterating through all digits (0-9) for each number of digits (3 to n). So, the time complexity is O(n), where 'n' is the input value.

Space Complexity:

• The code uses a 2D array dp with dimensions (1001 x 10) to store intermediate results. The space complexity is O(n) because the size of the array depends on the input 'n'.

In summary, the time complexity is O(n), and the space complexity is also O(n), where 'n' is the input value.