[알고리즘/동적 계획법] 10844 번 : 쉬운 계단 수 - python

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

10844번: 쉬운 계단 수

 

---

• 문제
• 소요시간: 45분 메모리초과 실패

 

---

• 설계하기(접근방법) 

1. n을 입력받는다

2. 알고리즘 해석

 

1의 자리

1 2 3 4 5 6 7 8 9

 

9 -> 1가지

 

(9 - 1) * 2 + 1 = 17

 

10의 자리

12 23 34 45 56 67 78 89 

10 21 32 43 54 65 76 87 98

 

10, 89 -> 2가지

 

(17 - 2) * 2 + 2 = 32

 

100의 자리

1가지만 확장 가능한 수들

210

989

789

 

1000의 자리

1가지만 확장 가능한 수들

1010

1210

3210

8789

8989

6789

 

즉 이전에 끝자리가 1이었거나 8인 수들이 현재 dp에서 끝자리가 0이나 9인 수가 된다

 

0 1 2 3 4 5 6 7 8 9 (끝자리수)

0 1 1 1 1 1 1 1 1 1    n = 1

1 1 2 2 2 2 2 2 2 1    n = 2 

2 3 4 4 4 4 4 4 3 2    n = 3

 

끝자리 0은 이전 dp의 1의 자리를 계승하고

끝자리 9는 이전 dp의 8의 자리를 계승한다

 

나머지 자리수는 현재 자리의 +1, -1인 이전 자리를 계승한다 즉

 

dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

dp[i][0] = dp[i-1][1]

dp[i][9] = dp[i-1][8] 이라는 규칙성을 가진다

 

3. dp[n]의 값을 더한 후 1,000,000,000을 나눈 나머지값을 출력한다

 

 

 

 

 

---

• 코드(출력)

메모리를 초과한 전수기록 코드이다.

n = int(input())

dp = [[] for _ in range(n+1)]
dp[1] = [1, 2, 3, 4, 5, 6, 7, 8, 9]

cnt = 0
for i in range(1, n):
    for j in dp[i]:
        if j % 10 == 0:
            dp[i+1].append(10*j + 1)
        elif j % 10 == 9:
            dp[i+1].append(10*j + 8)
        else:
            dp[i+1].append(10*j + j + 1)
            dp[i+1].append(10*j + j - 1)

print(len(dp[n]))

다른 분의 코드 참조

n = int(input())

dp = [[0] * 10 for _ in range(n+1)]

for i in range(1, 10):
    dp[1][i] = 1
for i in range(2, n + 1):
    for j in range(10):
        if j == 0:
            dp[i][j] = dp[i - 1][1]
        elif 1 <= j <= 8:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j + 1]
        else:
            dp[i][j] = dp[i-1][8]

print(sum(dp[n]) % 1000000000)

---

• 얻어갈 부분

1. 거의 다 접근했으나 전수조사로 메모리가 초과되었다. 빅오를 계산하여 나의 접근이 문제를 풀 수 있을지 생각해보자. 그렇지 않다면 다른 방법으로 접근하자