[백준no.10844]_쉬운계단수_python
문제
45656이란 수를 보자.
이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.
세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)
입력
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
[예제 입력]
1
1
출력
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다
[예제 출력]
1
9
풀이
[핵심 아이디어]
- 0~9까지의 숫자 중에서 각 숫자 앞 혹은 뒤에 올 수 있는 수의 개수는 각각 몇 개인지 따져봐야 함
- 옆에 올 수 있는 숫자의 수를 따져볼때, 0은 무조건 앞에 1 하나만 올 수 있고, 9 또한 앞에 8밖에 올 수 없음
- 2~8까지 숫자는 앞 뒤로 +1, -1 숫자가 올 수 있음
[풀이코드]
1
2
3
4
5
6
7
8
9
10
11
12
13
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] #0일때는 1만
elif j == 9:
dp[i][j] = dp[i-1][8] #9일때는 8만
else:
dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
print(sum(dp[N]) % 1000000000)
- 행렬을 활용하여 각 자릿 수에서의 경우의 수를 모두 합함
📌things that you can get from this problem
동적 계획법(Dynamic programming): 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용하는 방법
- 어떤 문제를 풀 때 작은 문제로 나누어서, 각각의 경우의 수를 구함
- 해당 방법으로 풀 경우, 재사용(즉, 저장하고 재사용)이 가능하기 때문에 시간 복잡도 개선됨
- 풀 수 있는 문제 유형:
- 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 도출 ex)최적 경로
- 동일한 작은 문제들이 반복 ex) 피보나치