백준 11057 (python): 오르막 수

 

n = int(input())
dp = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

# 두 자리 수일 땐  10  9  8  7  6  5  4 3 2 1 더했음
# 세 자리 수일 땐  55 45 36 28 21 15 10 6 3 1
# 네 자리 수일 땐 220 ...
# 패턴이 있다. 기존 dp[i-1]을 빼주면 된다.

newdp = [0 for i in range(10)]

for i in range(3, n+1):
    for j in range(10):
        if j == 0:
            newdp[j] = sum(dp)
        else:
            newdp[j] = newdp[j-1] - dp[j-1]
    dp = newdp[:] 
    # 배열의 깊은 복사 주의하기 ^^
    
if n == 1:
    print(10%10007)
else:
    print(sum(dp)%10007)

 

dp는 패턴을 찾아야 한다 ! ! ! 

그리고 메모리 제한이 있을 땐 재사용하자 -,-