이 문제는 5557 1학년 문제와 동일한 방법으로 풀 수 있다. DP의 유형중에 하나로 익혀놓아야 할 듯하다.
문제 이해 및 적용하기
입력으로 숫자의 자리수를 받고 각 자리들이 차이가 1씩만 나야하는 문제이다. 1학년 문제를 풀 때에 처음 풀어서 당황했던 기억이 나는 유형이다.
결국은 DP는 어떤 것을 저장해주고 꺼내써야할까? 이다.
여기에 대한 답편은 일의 자리에 0~9까지의 경우의 수를 1로 다 초기화시킨 다음에 자릿수를 하나씩 늘려가면서 이전 자릿수에서 경우의수를 받아오는 것이다. 1의자리로부터 10의 자리 경우의 수를 구하는 것을 보자.
이전 자릿수는 각각 경우의 수를 다음 자리수 dp list에 하나 높은것 하나 낮은 것에 보내준다.
마지막에 출력할 때에 DP[0]~DP[9]의 합을 구하고 그 합에서 DP[0]은 뺴주는 것을 주의하자
10의 자리에서 100의 자리의 경우의 수를 구하는 것도 동일함을 알 수 있다.
이런식으로 주어진 경우의 수까지 다 계산하면 된다.
본인은 문제의 한계치인 N이 100인 자리까지 다 미리 구해주었다.
# iterate dp
for i in range(99):
for j in range(10):
if j >= 1:
dp[i+1][j-1] += dp[i][j]
if j <= 8:
dp[i+1][j+1] += dp[i][j]
입력과 출력이며 출력을 할 때는 나머지를 하여 출력해주자
# input & output
n = int(input())
print((sum(dp[n-1])-dp[n-1][0])%1000000000)
주의할 점
- 마지막에 출력할 때에 DP[0]~DP[9]의 합을 구하고 그 합에서 DP[0]은 뺴주는 것을 잊지말자. 0의자릿수가 가장 앞인 것은 없으니까 말이다.
- 문제 마지막 조건에 나머지를 출력하는 것에 주의하자
전체코드
import sys
input = sys.stdin.readline
# make dp
dp = []
dp.append([1 for i in range(10)])
for i in range(99):
dp.append([0 for i in range(10)])
# iterate dp
for i in range(99):
for j in range(10):
if j >= 1:
dp[i+1][j-1] += dp[i][j]
if j <= 8:
dp[i+1][j+1] += dp[i][j]
# input & output
n = int(input())
print((sum(dp[n-1])-dp[n-1][0])%1000000000)