분류
다이나믹 프로그래밍(dp)
문제 설명
45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.
입력
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
입력 예시1
1
입력 예시2
2
출력
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
출력 예시1
9
출력 예시2
17
아이디어
-
3자리수까지 규칙 찾아보는데, _ _ _ 의 경우 아래와 같은 규칙 있지 않나...
- _ + 2자리 계단수
- 2자리 계단수 + _
그러면서 맨 앞에 0이 오는 경우랑 맨 뒤에 9가 오는 경우 이렇게 예외 챙겨주려고 했는데 도저히 점화식으로 만들 방법이 생각나질 않았음
-
결국 구글링 해봤다ㅠ
당연하게 dp 테이블을 1차원으로 생각했는데, 이 문제는 2차원 테이블로 푸는 게 관건인 듯!
길이가 i인 수에 대해,0~9 각각이 마지막에 들어갈 때만들 수 있는 계단수의 개수를 표로 그려보면 다음과 같음
-
표에서
d[i][j]는 양 상단 대각선 값의 합인 걸 확인할 수 있음이는 끝에 2가 오면 앞에는 하나 작은 1이나 하나 큰 3 둘 중에 올 수 있기 때문에 당연한 결과~
즉 하나 작은 자릿수
i-1에서 마지막 숫자가 내가 원하는 마지막 수j보다 하나 작은 경우j-1와 내가 원하는 마지막 수보다 하나 큰 경우j+1의 합이라는 것! -
단, 끝에 오는 수가
0이나9인 경우에는 각각j-1,j+1이 존재하지 않으므로 예외처리를 해주어야 함! -
최종 점화식은 아래와 같음
d[i][j] (i는 자릿수, j는 끝에 오는 수)
- 0 < j < 9 : d[i-1][j-1] + d[i-1][j+1] = d[i-1][1]
- j = 0 : d[i-1][j+1] = d[i-1][1]
- j = 9 : d[i-1][j-1] = d[i-1][8]
코드
n = int(input())
dp = [[0] * 10 for _ in range(n+1)] # [자릿수][끝에 오는 수]
dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] # 초기값
for i in range(2, n+1):
dp[i][0] = dp[i-1][1]
dp[i][9] = dp[i-1][8]
for j in range(1, 9):
dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
result = sum(dp[n]) % 1000000000
print(result)- dp 테이블이 2차원인 경우도 생각할 수 있어야 한다!!!
