[BOJ] 쉬운 계단 수 (no.10844)
문제
45656이란 수를 보자.
이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.
세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)
입력
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
🤔 생각
- 순회 중인 수에 대한 정보를 저장하고 있어야 한다.
- 따라서 dp 배열을 2차원으로 구성해야겠다.
메모이제이션
dp[i][j] : 길이가 i이고 순회 중인 수가 j일 때 계단수 갯수
케이스
- 이전 수보다 1 작게
- 이전 수보다 1 크게
+) 0,9 등 극단값은 따로 조건문으로 처리
🔥 점화식
dp[i] = dp[i-1][j-1] + dp[i-1][j+1]
📌 내 풀이
import sys
input = sys.stdin.readline
N = int(input())
dp = [[0]*10 for _ in range(N+1)]
dp[1] = [0,1,1,1,1,1,1,1,1,1]
for i in range(2,N+1):
for j in range(10):
if j == 0:
dp[i][j] = dp[i-1][j+1]
elif j == 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)
✔ 회고
- 2차원 배열을 사용한 DP를 복습할 수 있었다.
Author And Source
이 문제에 관하여([BOJ] 쉬운 계단 수 (no.10844)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@wisepine/BOJ-쉬운-계단-수-no.10844저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)