BOJ 10844 쉬운 계단 수
5574 단어 2021.01.132021.01.13
https://www.acmicpc.net/problem/9471
시간 1초, 메모리 128MB
input :
- N ( 1 <= N <= 100)
output :
- 정답을 1,000,000,000으로 나눈 나머지를 출력
조건 :
- 45656
- 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수 (0으로 시작 불가능)
- 수의 길이가 N인 계단 수가 몇 개??
어떠한 숫자가 9가 아닌 이상 계단 수로 가능한 것은 2가지 이다.
n -> n - 1 / n + 1
그러면 이것을 어떻게 리스트로 나타낼 것인가?
그냥 숫자를 곱하거나 더해서 만드는 건 불가능 할 것 같고.
숫자의 맨 뒷자리를 리스트 인덱스로 분류해서 계산하자.
어차피 숫자의 최대 길이는 100이니까 최대로 리스트를 만들어도 1000 밖에 되지 않는다.
바텀업 방식으로 모든 경우를 다 만든 다음에 마지막에 출력할 때 전체 행을 게산하도록 하자.
import sys
T = int(sys.stdin.readline())
dp = [[0] * 10 for _ in range(101)]
for i in range(10):
dp[1][i] = 1
for x in range(2, 101):
for y in range(10):
up = y + 1
down = y - 1
if down >= 0:
dp[x][down] += dp[x - 1][y]
if up < 10:
dp[x][up] += dp[x - 1][y]
res = 0
for i in range(10):
res += dp[T][i]
print((res - dp[T][0]) % 1000000000)
경우만 신경 쓰지 말고. DP를 어떻게 구성할 지도 생각하면서 문제를 보자.
Author And Source
이 문제에 관하여(BOJ 10844 쉬운 계단 수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsin2475/BOJ-10844-쉬운-계단-수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)