[백준] 10844번 쉬운 계단 수 파이썬(Python) 풀이

10844번: 쉬운 계단 수

---

[문제]

---

[코드]

N = int(input())

dp = [[0]*10 for _ in range(N+1)]
for i in range(1, 10):
    dp[1][i] = 1

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

        elif j == 9:
            dp[i][j] = dp[i-1][8]

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

print(sum(dp[N]) % 1000000000)

---

[해설]

다이나믹 프로그래밍 문제이다

문제의 핵심 간단하다 아래의 그림을 참고하자

 

출처 : https://cotak.tistory.com/12

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

문제를 살펴보면 n =1 일때

1~9 까지의 하나씩만 사용해서 만들 수 있기 때문에 9개를 만들 수 있다

이를 dp로 표현하면 dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]이다 

 

그리고 n=2 일때를 살펴 보면 

dp[2][0]은 1가지

dp[2][1]~[8]은 2가지

dp[2][9]는 1가지를 갖을 수 있을 것을 확인할 수 있다

즉, dp[2] = [1, 2, 2, 2, 2, 2, 2, 2, 2, 1]인 것이다

 

n=3일때는 이를 반복해서 더해주면 된다

 

결국 이를 수식으로 정리하자면 아래와 같다

i)j == 0

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

 

ii) j== 1~8

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

 

iii) j == 9

dp[i][j=9] = dp[i-1][8]

(약간 신경망 모델 같기도..?)

 

이를 코드로 표현하면 아래와 같다

N = int(input())

dp = [[0]*10 for _ in range(N+1)]
for i in range(1, 10):
    dp[1][i] = 1

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

        elif j == 9:
            dp[i][j] = dp[i-1][8]

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

print(sum(dp[N]) % 1000000000)