[백준] 11057번 문제 (오르막 수) 파이썬(Python) 풀이

dp = [[0] * 10 for i in range(1001)]

n = int(input())

for i in range(10):
    dp[1][i] = 1

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

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

 

우선 경우의 수를 메모장에 적어가며 규칙을 찾았다.

규칙은 해당 자리수의 숫자가 오르막 수일 때 맨 뒤에 오는 숫자에 대해 사용된 횟수를 적으면 알 수 있다. 그것을 표로 나타내면 아래와 같다.

 

	0	1	2	3	4	5	6	7	8	9
자리수 1	1	1	1	1	1	1	1	1	1	1
자리수 2	1	2	3	4	5	6	7	8	9	10
자리수 3	1	3	6	10	15	21	28	36	45	55

해당 표를 보니 규칙을 쉽게 알 수 있다.

 

자리수가 1개인 경우는 당연히 각 숫자가 한 번씩 올 수 있으니 0 ~ 9 까지 한 번씩만 사용되고,

자리수가 2개인 경우부터는 표를 기준으로 해당 숫자의 위에 있는 수와 왼쪽에 있는 수를 더한 값이 된다. 자리수가 3인 경우에 더 쉽게 확인할 수 있다. 

 

이것을 코드로 나타내면 아래와 같다.

dp[i][j] = dp[i-1][j] + dp[i][j-1]

단, 숫자가 0이 마지막에 오는 경우는 한 번이므로 해당 조건만 처리하고 반복문으로 처리하면 된다.