[백준] 10844번: 쉬운 계단 수 - python

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

10844번: 쉬운 계단 수

처음 생각한 아이디어

 

처음에 무지성으로 고딩때 풀던 점화식마냥 찍어서 작성한 코드.

 

 

무지성 찍기가 난이도가 높아질 수록 통하지 않는 듯 하다.

n = int(input())

dp = [0] * (n+1)
dp[1] = 9
dp[2] = 17 #12 23 34 45 56 67 78 89 * 2 + 10
for i in range(2, n+1):
    dp[i] = (dp[i-1]-1) * 2 +1

print(dp[n])

 

그다음 생각한 아이디어

 

전에 푼 정수 삼각형처럼 값을 계속해서 증가 시켜가면서 작성하면 어떨까 라는 생각으로 작성했다. 

 

n = int(input())

dp = [[0] * 10 for _ in range(n+1)] #0 1 2 3 4 5 6 7 8 9 

for i in range(1, 10):
    dp[1][i] = 1 # 1 2 3 4 5 6 7 8 9 0제외

for i in range(2, n+1):
    for j in range(10):
        if j == 0: #0일때 
            dp[i][j] += dp[i-1][j+1]
        elif j == 9: #마지막 9일때
            dp[i][j] += dp[i-1][j-1]
        else: #나머지일때
            dp[i][j] += (dp[i-1][j+1] + dp[i-1][j-1])

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

 

완성..

DP 너무 어렵다