[Python] 백준 #110570- 오르막 수

문제

---

11057번: 오르막 수

코드

---

My answer

from sys import stdin

n = int(stdin.readline())
tmp=[i for i in range(1,10)]
dp= [[0] * 10 for _ in range(n + 1)]
dp[0]=[1,1,1,1,1,1,1,1,1,1]
for i in range(1,n+1):
    for j in range(0,10):
        if(j==0):
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=dp[i][j-1]+dp[i-1][j]
#print(dp[n-1])
print(sum(dp[n-1])%10007)

Another answer

n = int(input())
a = [1]*10
for j in range(1,n):
    for i in range(1,10):
        a[i] += a[i-1]
print(sum(a)%10007)

 

풀이

---

바로 전에 쉬운계단수를 해결하고 나니까 엄청 쉬웠다. 거의 푸는 방법이 동일했기 때문이다. 우선 나는 이전문제처럼 dp[i][j]에서 i를 자릿수,j를 끝자리로 계산을 해봤다. 아 그리고 우선 말해둘 것이 맨처음에 문제를 맞게 푼것같은데 틀렸었는데 그 이유는 문제안에 수는 0으로 시작할 수 있다. 라는 이상한 조건때문이었다;; 이걸 생각하고 풀이를 해보겠다. 우선 자릿수가 1이고 끝자리가0인 dp[1][0]은 0으로 하나 dp[1][1]도 1로하나. 이렇게 dp[1]배열은 전부 자기자신 하나이므로 1이 나온다. 이후 dp[2][0]은 00으로 한개, dp[2][1]은 01,11로 두개이다. 이 01은 dp[1][0]에 1을 붙인것 11은 dp[1][1]에 1을 붙인것이다. 이런식으로 반복하다보면 dp[i][j]는 dp[i][j-1]+dp[i-1][j]라는 식을 얻을 수 있다. 끝자리가 0인 경우만 예외로 무조건 1이다. 나는 이렇게 2차원배열로 쉬운계단수와 동일하게 생각해서 풀었는데, 아래 코드는 똑같은데 이걸 1차원 배열에서 구현했다. 같은 방법도 이렇게 단순하게 만드는 것도 정말 멋있다... 메모리도 훨씩 적게 들고..부럽다..