[백준] 11057번: 오르막 수

💻 문제 - S1

오름차순으로 N의 길이를 가지는 오르막 수를 구하는 프로그램이다. 끝자리 수가 추가되거나 바뀔 때 개수의 관계를 다음과 같이 나타낼 수 있다.

자리수/끝자리 수	0	1	2	3	4	5	6	7	8	9
dp[1]	1	1	1	1	1	1	1	1	1	1
dp[2]	1	2	3	4	5	6	7	8	9	10
dp[3]	1	3	6	10	15	21	28	36	45	55
...

예를 들어, dp[2][2]의 경우 02, 12, 22로 3개이고 dp[3][1]의 경우 001, 011, 111로 3개이다. dp[3][2]의 경우 022, 122, 222(끝자리 추가)/002, 012, 112(끝자리 변경)로 6개이다.

이를 통해, dp[i][j] = dp[i-1][j] + dp[i][j-1]과 같은 점화식을 얻었다.

---

👉 제출 코드

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

---

🙏 다른 사람의 풀이 보기

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

이차원 배열을 사용하지 않아도 갱신 전 숫자를 사용할 수 있으므로 이전 숫자들의 합으로 구현이 가능하다.