백준 11057 오르막 수 python 파이썬 @@황소처럼우직하게 @@숏코딩

n = int(input())

dp = [[0 for i in range(10)] for j in range(n)]
dp[0] = [1 for i in range(10)]

for i in range(1, n):
    for j in range(10):
        for k in range(j, 10):
            dp[i][k] += dp[i - 1][j]

print(sum(dp[-1]) % 10007)

 우선 dp 배열 만들어주는데, 어떻게 만드냐면

[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 

[1, 3, 6, 10, 15, 21, 28, 36, 45, 55]] 

이런식으로 쌓이게끔 해서 마지막 배열 합계가 정답입니다.  ( % 10007 잊지말구요)

 

해결 아이디어

0에서 다음 숫자 1, 2, ..., 8, 9 될 수 있죠. i 배열에서 1번인덱스~9번인덱스에, i - 1배열에 0번인덱스 값을 더해줍니다.

1에서 다음 숫자 2, 3, ..., 8, 9 될 수 있쬬. i 배열에서 2번인덱스~9번인덱스에, i - 1배열에 1번인덱스 값을 더해줍ㄴ다.

...

 

뭔가 시간초과나진 않을까 걱정했는데, 그냥 이렇게 풀어도 되네요.