https://www.acmicpc.net/problem/10844
문제
45656이란 수를 보자.
이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오.
(0으로 시작하는 수는 없다.).
풀이
1) 문제를 한글로 풀어본다.
D(N) = 길이가 N인 계단 수의 개수
2) 점화식을 만든다.
D[N][L] = D[N-1][L-1] + D[N-1][L+1]
L = 0 : D[N][L] = D[N - 1][L + 1]
L = (1 ~ 8) : D[N][L] = D[N - 1][L - 1] + D[N - 1][L + 1]
L = 9 : D[N][L] = D[N - 1][L - 1]
3) 코딩
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* 쉬운 계단 수
* https://www.acmicpc.net/problem/10844
*
* 문제
* 45656이란 수를 보자.
* 이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.
* 세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.
* N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)
*
* 입력
* 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
*
* 출력
* 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
*
* 예제 입력 1
* 1
* 예제 출력 1
* 9
* 예제 입력 2
* 2
* 예제 출력 2
* 17
*/
public class BOJ_10844_쉬운계단수 {
static final long MOD = 1000000000;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
long[][] d = new long[n+1][10];
for (int i = 1; i <= 9; i++) {
d[1][i] = 1;
}
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= 9; j++) {
d[i][j] = 0;
if (j - 1 >= 0) d[i][j] += d[i-1][j-1];
if (j + 1 <= 9) d[i][j] += d[i-1][j+1];
d[i][j] %= MOD;
}
}
long result = 0;
for (int i = 0; i <= 9; i++) {
result += d[n][i];
}
result %= MOD;
System.out.println(result);
}
}
'ALGORITHM > DP' 카테고리의 다른 글
11052번 - 붕어빵 판매하기 (0) | 2018.07.21 |
---|---|
11727번 - 2×n 타일링 2 (0) | 2018.07.21 |
11726번 - 2×n 타일링 (0) | 2018.07.21 |
1463 - 1로 만들기 성공 (0) | 2018.07.20 |