백준(baekjoon) 10844번: 쉬운 계단 수(실버 1, 파이썬 PYTHON) - 동적 계획법 1

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

 

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

10844번: 쉬운 계단 수

 

import sys

N=int(sys.stdin.readline())
arr=[[0 for _ in range(10)]for _ in range(N+1)]
result=0

for x in range(1,10):
  arr[1][x]=1

for x in range(2,N+1):
  for y in range(10):
    if(y==0):
      arr[x][y]=arr[x-1][y+1]
    elif(y==9):
      arr[x][y]=arr[x-1][y-1]
    else:
      arr[x][y]=arr[x-1][y-1]+arr[x-1][y+1]

for x in arr[N]:
  result+=x

print(result%1000000000)

 

※ 동적 계획법 1

 

 

● 숫자 길이 N을 입력받은 후, 초기값이 0이고 인덱스 0~N 까지의 행과 인덱스 0~9 까지의 열의 크기를 가지는 arr 배열을 정의해준다. 이 때 arr 의 행의 인덱스는 숫자의 길이를, 열의 인덱스는 끝 자리 숫자를 의미한다. 그리고 마지막에 arr 배열 N 번째 행에 있는 모든 요소의 합을 저장할 result 변수를 0으로 초기화해준다.

 

● 우선 행의 인덱스가 1인 경우(숫자의 길이가 1), 수의 끝 자리에는 0을 제외한 모든 수가 올 수 있으므로 열의 인덱스 0인 요소를 제외한 모든 요소를 1로 갱신해준다.

 

● 그 후 행의 인덱스를 가리키는 x는 2부터 N 까지, 열의 인덱스를 가리키는 y는 0부터 9까지 탐색을 시작한다.

 

case 1: y가 0일 때

-> 수 길이가 x인 수가 끝자리 숫자가 0이고 계단수를 만족하려면, 수 길이가 x-1 이고 끝 자리 숫자가 1인 수에 0을 붙이는 경우만 가능하므로 arr[x][y] 의 값을 arr[x-1][y+1] 로 갱신해준다.

 

case 2: y가 9일 때

-> 수 길이가 x인 수가 끝자리 숫자가 9이고 계단수를 만족하려면, 수 길이가 x-1 이고 끝 자리 숫자가 8인 수에 9을 붙이는 경우만 가능하므로 arr[x][y] 의 값을 arr[x-1][y-1] 로 갱신해준다.

 

case 3: y가 1부터 8까지의 수 중 하나일 때

-> 수 길이가 x인 수가 끝자리 숫자가 1부터 8중 하나이고 계단수를 만족하려면, 수 길이가 x-1 이고 끝 자리 숫자가 y-1 인 수에 y를 붙이는 경우, 수 길이가 x-1 이고 끝 자리 숫자가 y+1 인 수에 y를 붙이는 경우의 총 두 가지 경우가 가능하므로 arr[x][y] 의 값을 arr[x-1][y-1]+arr[x-1][y+1] 로 갱신해준다. 

 

● 그 후 arr 배열 N번째 행에 있는 모든 요소의 값을 더해주면 수 길이가 N인 계단수의 개수가 나오게 된다. 이 값을 1000000000 으로 나눈 나머지를 출력해주면 답을 구할 수 있다!

 

 

결과