BOJ(오르막 수)(11057)

작성일 | In

오르막 수

  • 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이 때, 인접한 수가 같아도 오름차순으로 친다
  • 2234,3678,1119는 오르막 수 이지만, 2232,3676,91111은 오르막 수가 아니다.
  • 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오 No Image
n = int(input())
d = [[0]*10 for _ in range(n+1)]
mod = 10007
def solve():
    for i in range(10):
        d[1][i] = 1
    for i in range(2, n+1):
        for j in range(10):
            for k in range(j+1):
                d[i][j] += d[i-1][k]
            d[i][j] %= mod
solve()
print(sum(d[n]) % mod)

다른 풀이 방법

n = int(input())

d = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
for i in range(n):
    temp = list()
    s = 0
    for j in range(10):
        s += d[i][j]
        temp.append(s)
    d.append(temp)
print(sum(d[n-1])%10007)

참고자료 codeplus

0%