[백준] 10844 - 쉬운 계단 수 (Python)

문제 출처 :

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

문제 풀이 :

• 전형적인 DP문제이다. 다만 처음 DP를 풀었다면 2차원으로 볼 생각을 못해서 어려웠을 꺼 같은데 저번에 2차원으로 푼 경험이 있기 때문에 2차원 배열을 이용한 DP로 문제를 풀었다.
• DP 문제는 식을 세우기만 하면 의외로 쉽게 풀리는 경향이 있는듯 하다. 
  다음과 같이 DP식을 정하고 규칙을 찾아보았다.
• DP[i][j] = 길이 i에 가장 오른쪽 자리 숫자가 j 일때 존재하는 계단수의 개수

i/j	0	1	2	3	4	5	6	7	8	9
1	0	1	1	1	1	1	1	1	1	1
2	1	1	2	2	2	2	2	2	2	1
3	1	3	..	..	..	..	..	..	..	..

• 위의 표를 보면 3가지 경우를 j가 0인경우,9인경우, 나머지 경우 로 볼 수 있다.
  j=0 인 경우는 -1 할 수 없으므로 +1만
  j=9 인 경우는 +1 할 수 없으므로 -1만
  나머지의 경우는 +1,-1를 하는 경우로 점화식을 세워서 해결하였다.

n=int(input())

dp =[[-1]*11 for _ in range(102)]

#init
dp[1][0]=0
for i in range(1,10):
    dp[1][i]=1

dp[2][0]=1
dp[2][1]=1
for i in range(2,9):
    dp[2][i]=2
dp[2][9]=1


def solve(N,idx):
    global dp

    if(dp[N][idx]!=-1):
        return dp[N][idx]

    if(idx==0):
        dp[N][idx] = solve(N-1,idx+1)
    elif(idx==9):
        dp[N][idx] = solve(N-1,idx-1)
    else:
        dp[N][idx] = solve(N-1,idx-1)+solve(N-1,idx+1)

    return dp[N][idx]

ans=0
for i in range(10):
    ans += solve(n,i)

print(ans%1000000000)