[Algorithm][Python] 백준(BOJ) 10844 쉬운 계단 수

[문제]

https://www.acmicpc.net/problem/10844

---

[내 코드]

DP 문제

• 자릿수 1부터 4까지 하나하나 써보다 보니 첫째자리 수 이후로 중복이 되는 현상을 발견했다. 그래서 시작하는 숫자 / 자릿수 로 이차원 배열을 사용하면 식을 작성할 수 있을 것 같았다.
  
• 0으로 시작하는 수는 ( 자릿수 -1 )의 1로 시작하는 개수와 같다.
  
• 나머지는 (자릿수 -1 )의 대각 수의 합과 같다.
  
• 시작하는 수로 10을 둔 이유는 9의 경우에는 다음 올 수 있는 수는 8뿐이고, 대각 숫자의 합을 계산할 때 범위 오류를 피하고 다른 조건식을 쓰지 않기 위함이다.
  
• 열을 시작하는 숫자 0~9 , 행을 자릿수를 기준으로 표를 그려보면 다음과 같이 나온다.

시작하는 숫자 / 자릿수	0	1	2	3	4	5	6	7	8	9	10
1	0	1	1	1	1	1	1	1	1	1	0
2	1	2	2	2	2	2	2	2	2	1	0
3	2	3	4	4	4	4	4	4	3	2	0
4	3	6	7	8	8	8	8	7	6	3	0

ar = []

# 초기화
for row in range(101):
    ar.append([])
    for col in range(11):
        ar[row].append(0)

for j in range(10):
    ar[1][j] = 1

for i in range(2, 101):
    ar[i][0] = ar[i-1][1];
    for j in range(1,10):
        ar[i][j] = ar[i-1][j-1] + ar[i-1][j+1]

# for i in range(len(ar)):
#     for j in range(len(ar[i])):
#         print(ar[i][j], end=' ')
#     print()

n = int(input())
sum = 0

for i in range(1, 10):
    sum += ar[n][i]

print(sum%1000000000)

위의 코드는 n의 입력값과 무관하게 100까지의 모든 경우를 계산하는 코드이다.
range를 100으로 하는 대신 n으로 하도록 했다.

### 개선

n = int(input())
sum = 0

ar = []

# 초기화
for row in range(n+1):
    ar.append([])
    for col in range(11):
        ar[row].append(0)

for j in range(10):
    ar[1][j] = 1

for i in range(2, n+1):
    ar[i][0] = ar[i-1][1];
    for j in range(1,10):
        ar[i][j] = ar[i-1][j-1] + ar[i-1][j+1]

for i in range(1, 10):
    sum += ar[n][i]

print(sum%1000000000)

range 를 바꿨음에도 메모리가 변하지 않았다. n이 100이라서 크게 차이가 없는 것 같다.