[백준/BOJ] 백준 코딩 알고리즘 10844번 쉬운 계단 수 Python 다이나믹 프로그래밍

 

나의 풀이

우선 자릿수 에 따라서 계단수가 어떻게 늘어나는지 그려볼 수 있다

그러면 각 자릿수 의 앞의 자리 수에 있는 값에 따라서 경우의 수가 1개 혹은 2개로 달라지는 것을 알 수 있다

 

이를 다시 정리해본다면

현재 자릿수의 값에 따라서 언제 등장하는지 나눌 수 있다

 

현재 자릿수 값이 0이라면, 앞의 자릿수가 1일 때만 등장할 수 있고

현재 자릿수 값이 9라면, 앞의 자릿수가 8일 때만 등장할 수 있다

그 외 현재 자릿수 값이 n (n=1~8)이라면, 앞의 자릿수가 n-1일 때 혹은 n+1일때 등장할 수 있다

 

그리고 이를 코드로 다시 정리한다면 아래와 같다

 

 

dp 배열은 2차원 배열로 구성되고

 

첫 번째 차원은 자리수

두 번째 차원은 어떤 수가 나왔는지를 의미한다

그리고 해당 위치에는 그 경우에 따른 경우의 수를 저장한다

 

이를 코드로 나타내면 아래의 #계산 주석이 있는 부분과 같다

 

import sys

def input():
  return sys.stdin.readline().rstrip()

N = int(input())
DIV = 1000000000

stairs = [[0] * 10 for i in range(N + 1)]

# 초기값 설정
for i in range(1, 10):
  stairs[1][i] = 1

# 계산
if N >= 2:
  for i in range(2, N + 1):
    for j in range(10):
      if j == 0:
        stairs[i][j] = stairs[i - 1][1]
      elif j == 9:
        stairs[i][j] = stairs[i - 1][8]
      else:
        stairs[i][j] = (stairs[i - 1][j - 1] + stairs[i - 1][j + 1])

# 답 출력
total = 0
for i in range(10):
  # print(f"[{N}][{i}]: {stairs[N][i]}")
  total += stairs[N][i]
print(total % DIV)

우선 초기값으로 한 자리수일 때 1~9까지 값에 대하여 모두 1의 경우의 수 값을 저장해준다

그리고 입력값에서 요구하는 N의 크기가 2이상일 때, 경우의 수를 반복문을 통해 계산하기 시작한다

모든 경우의 수에 대하여 계산이 끝났다면, 다시 for문을 돌아서 총 값을 저장하고, DIV값으로 나누어 답을 출력한다

 

참고: https://cotak.tistory.com/12

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