[algorithm] 파이썬 - 백준 11057

'오르막 수'

코드1

n = int(input())
d = [[0 for i in range(10)] for i in range(n+1)]
d[1] = [1 for i in range(10)]
if n > 1:
    d[2] = [i for i in range(10, -1, -1)]

    for i in range(3, n+1):
        for j in range(10):
            temp = 0
            for k in range(j):
                temp += d[i-1][k]
            d[i][j] = sum(d[i-1]) - temp

print(sum(d[n]) % 10007)

풀이

 

 

dp테이블을 위와 같은 표처럼 2차원으로 구현했다. 블로그 포스팅을 위해 표를 그리다보니 처음에 생각했던 점화식은

d[i][2] = sum(d[i-1]) - (d[i-1][0] + d[i-1][1]) 이런 식이었는데

d[i][2] = d[i][1]-d[i-1][1] 로 풀어서 위의 코드처럼 k 반복문을 돌지 않아도 된다는 것을 알았다.

 

그래서 코드를 아래와 같이 바꿔주었더니 채점 시간이 더 빨라졌다

코드2

n = int(input())
d = [[0 for i in range(10)] for i in range(n+1)]
d[1] = [1 for i in range(10)]
if n > 1:
    d[2] = [i for i in range(10, -1, -1)]

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

print(sum(d[n]) % 10007)