[백준/DP] 11057번: 오르막 수 (실버1, python)

https://www.acmicpc.net/problem/11057

11057번: 오르막 수

아이디어

DP문제였다.. 규칙을 못 찾아서 검색했다 ㅠㅠ..

	0	1	2	3	4	5	6	7	8	9	total
N = 1	1	1	1	1	1	1	1	1	1	1	10
N = 2	1	2	3	4	5	6	7	8	9	10	55
N = 3	1	3	6	10	15	21	28	36	45	55	220

 

행은 길이가 N일 때

열은 해당 숫자로 끝나는 경우의 수이다.

 

이 표에서 찾을 수 있는 규칙은 다음과 같다.

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

 

* 0일때 경우의 수는 계속 1개니까 (0, 00, 000, 0000...) 점화식을 사용해도 문제가 없다.

 

전체 코드

N = int(input())

dp = [1] * 10

for _ in range(1, N):
    for j in range(1, 10):
        dp[j] += dp[j-1]
    

print(sum(dp) % 10007)

 

찾은 점화식은 [i][j] = [i-1][j] + [i][j-1]인데 코드 상에서 dp[j] += dp[j-1]인 이유는 2차원 배열로 구하지 않고 i-1의 배열에서 바로 값을 구하기 때문이다. (i-1의 배열의 원래 값에 j-1을 더하기 때문에 [i-1][j] + [i][j-1]이 된다. )