문제링크 : https://www.acmicpc.net/problem/10844
목표:
- 바로 옆에 있는 수들의 차이는 1
- 길이가 주어졌을 때 그런 수열들의 개수 구함
조건:
- 첫 숫자는 0이 될 수 없음.
- N은 1보다 크거나 같고, 100보다 작거나 같은 자연수
solution 설명 :
공간복잡도 D[N][10]
이차원 배열사용
- 주 idea
- number_of_cases[N][L] : 마지막 수가 L인 N자리 계단수를 의미한다.
- 값 넣어논다.
N = int(input())
number_of_cases = [[0] * 10 for _ in range(N+1)]
for i in range(1,10):
number_of_cases[1][i] = 1
# 마지막수가 i인 1자리 수
for j in range(2,N+1):
for k in range(0,10):
if k is 0 :
number_of_cases[j][k] += number_of_cases[j-1][k+1]
elif k is 9 :
number_of_cases[j][k] += number_of_cases[j-1][k-1]
else: k>=1:
number_of_cases[j][k] += (number_of_cases[j-1][k+1] +number_of_cases[j-1][k-1])
위에 for문을 이제 좀 더 우아하게 만들면
for j in range(2,N+1):
for k in range(0,10):
if k+1 <= 9:
number_of_cases[j][k] += number_of_cases[j-1][k+1]
if k-1 >= 0:
number_of_cases[j][k] += number_of_cases[j-1][k-1]
마지막 합 구하는 식은
ans = 0
for p in range(0,10):
ans += number_of_cases[N][p]
print(ans%1000000000)
마지막에 ans에 반드시 %1000000000해줘야한다.
공간복잡도 O(10)
일차원 배열사용
m=[0]+[1]*9
for i in range(int(input())-1):
m=[m[1]]+[m[i-1]+m[i+1]for i in range(1,9)]+[m[8]]
print(sum(m)%1000000000)