[백준/BOJ] - 10844번 python 풀이 - dp

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

10844번: 쉬운 계단 수

---

---

규칙 찾는 것이 중요한 dp 문제이다.

dp 문제를 해결하기 위해선 점화식 즉, 규칙을 먼저 찾는 것이 중요하다.

그렇기에 표를 만들고 n이 1,2 일 경우를 직접 채워 넣어 어떤 규칙이 있는지 찾아보자.

 

아래 코드에는 행을 n으로 하고 열을 0~9로 했으나 예시 그림은 반전 형태이다.

 

해당 그림에선 행(가로)이 맨 끝에 무엇이 올지, 열(n값)이다.

앞선 열의 행값 맨끝값 0 or 2에 위치한 값을 더하면 다음 열의 맨 끝에 1을 넣을 수 있는 경우의 수를 구할 수 있다.

 

하지만 다음 열의 맨끝 값에 0을 넣을 수 있는 경우의 수는

앞선 값이 1인 경우 밖에 없다.

그렇기에 코드 짤 때 예외처리를 해야한다.

 

동일하게 다음 열의 맨 끝값에 9를 넣을 수 있는 경우의 수는 8 뿐이므로

예외처리 필!

 

---

""

"""
1. 아이디어
n에 따라 만들 수 있는 경우의 수를 배열에 입력.
(n=1) 맨 처음은 0만 올 수 없으므로 1~9 9개.
(n=2) 앞 행에 저장되어있는 값을 참고한다. 앞행 속 값 기준 열 +- 1 값을 모두 더하여 저장.
※ 끝값이 0이거나 9일 경우엔 각 1개밖에 생성되지 않음을 인지 -> 예외처리

2. 시간복잡도

3. 자료구조
dp
"""
import sys
n = int(input())
dp = [[0]*10 for _ in range(n)]
#가로 마지막 뭐들어갔는지
#세로 n값
for i in range(1,10): #1~9 #기본 세팅값
    dp[0][i] = 1
if n>=2:
    for a in range(1,n):#n=2면 2줄만 있어도 됨
        for b in range(10):
            if b==0:
                dp[a][b] = dp[a-1][b+1]
            elif b==9:
                dp[a][b] = dp[a-1][b-1]
            else:
                dp[a][b] = dp[a-1][b-1] + dp[a-1][b+1]    
print(sum(dp[n-1])%1000000000)