✔ 문제 #10844. 쉬운 계단의 수
input : N (1≤N≤100)
output: 정답을 1,000,000,000로 나눈 나머지
input
1
1
1
2
output
1
9
1
17
✔ 풀이과정
모든 경우의 수를 구하는 것이다. 근데 하나하나 다 풀려고 하면 너무 복잡해진다.
각각의 케이스를 구해보자. N이 1일 때, 자리수가 1이기 때문에 각 숫자들이 맨 뒷자리에 올 수 있는 개수는 1씩이다.
- 맨 뒤에 0이 올 수 있는 경우의 수 - 0으로 시작할 수 없고, 1만 올 수 있다. ⇒ (1개)
- 맨 뒤에 1이 올 수 있는 경우의 수 - 21가 올 수 있다. 01은 올 수 없다. ⇒(1개)
- 맨 뒤에 2가 올 수 있는 경우의 수 - 12, 32가 올 수 있다. ⇒(2개)
- 맨 뒤에 9이 올 수 있는 경우의 수 - 8만 올 수 있다. ⇒(1개)
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 1 |
| 3 | 1 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 3 | 2 |
내 풀이
내가 처음 한 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n = int(input())
num = [[0]*10 for _ in range(n+1)]
num[0] = [1,1,1,1,1,1,1,1,0]
for i in range(1,n+1):
for j in range(10):
if j == 0:
num[i][j] = num[i-1][j+1]
elif j == 9:
num[i][j] = num[i-1][j-1]
else:
num[i][j] = num[i-1][j-1] + num[i-1][j]
answer = sum(num[n]) % 100000000
print(answer)
이 풀이는 런타임에러가 난다.
다른 풀이 #1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n = int(input())
num = [[0]*10 for _ in range(n+1)]
num[0] = [0,1,1,1,1,1,1,1,1]
for i in range(1,n+1):
for j in range(10):
if j == 0:
num[i][j] = num[i-1][j+1]
elif j == 9:
num[i][j] = num[i-1][j-1]
else:
num[i][j] = num[i-1][j-1] + num[i-1][j+1]
answer = sum(num[n]) % 100000000
print(answer)
✔ 회고
동적계획법 (Dynamic Programming, DP)
- 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법
- 모든 방법을 일일이 검토하여 최적의 해를 찾아내는 방식
- ↔ 그리디알고리즘과 반대 (모든 해를 구하지 않고, 닥치는 순간만 구함)
- 그리디 알고리즘에 비해 시간은 오래 걸리지만, 결과적으로 항상 최적의 해를 구할 수 있음
- ex. 피보나치 수열
이 문제는 동적계획법에 대한 예제이다. 직접 다 풀지는 못했지만, 동적계획법이 어떤 것인지 알게 되었다.
여러 번 반복되는 경우, 테이블이나 배열을 이용하여 기억공간에 저장해두었다가 불러올 수 있다는 것을 알게 되었다.