(파이썬) 백준 10844 쉬운 계단 수 파이썬 풀이

백준 10844번

풀이

우선, 문제를 이해하는 데 조금 오래 걸렸다. 1의 자리 수일 때는 0을 제외한 모든 수가 계단수가 된다고 가정해야 두번째 자리의 계단 수를 찾을 수 있게 된다. 

 

그리고, 자리수가 늘어날 때마다 1의자리수가 가장 왼쪽부터 시작한다고 생각하면 된다.

 

2자리 수일 때

0 옆에 올 수 있는 것은 1로 하나다, 1 옆에는 0과 1,  2부터 계속 두개씩 나오다가 9일 때는 8만 올 수 있다.

 

3자리 수일 때도 마찬가지일 것이다.

 

그렇다면 dp배열에다가 1자리 수를 입력해 놓고, 자리 수가 늘어날 때마다 i-1, i+1일 때의 경우를 합쳐주면 된다는 사실을 알 수 있다. 다만 숫자가 0일 때와 9일 때는 각각 1일때, 8일때의 값만 계산해야 한다.  

 

1. 자리 수를 a변수에 입력한다.

a = int(input())

 

2. dp배열에 0~9까지의 가지수를 자리 수만큼 넣을 수 있게 생성한다. (문제에 자리수의 최댓값을 100으로 한정)

dp = [[0 for i in range(10)]for i in range(101)]

 

3. 자리수가 1일때의 값을 입력해 놓는다.

for i in range(1,10):

  dp[1][i]=1

#1자리 수 일 때 0, 1, 1, 1, 1, 1, 1, 1, 1, 1를 입력

 

4. 2자리 수부터 계산한다. i는 자리수이다.

숫자가 0일 때, 9일 때만 따로하고 나머지는 +-1의 값들을 모은다.

 

for i in range(2,a+1):#1은 1의자리일 때 위의 입력해 놓았다. i는 자리수

  for j in range(10): #j는 0~9까지의 수

    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[a])%1000000000)

 

다 더한 것이 가짓수의 개수이고, 1,000,000,000으로 나눈 값의 나머지를 출력한다.