문제

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

---

입력

첫째 줄에 N이 주어진다.

---

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

---

풀이

제한조건

• N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

접근방법

DP
단서를 살펴보자.

• 인접한 자리 수의 차이가 1.
• 정답을 1,000,000,000 으로 나눈 나머지.
• N이 1~100으로 매우 작으나, 1초-256MB 제한
  DP의 향기가 솔솔난다.

확신을 가지기 위해 직접 나열하며 생각을 해보자.

N == 1
1, 2, 3, 4, 5, 6, 7, 8, 9 => 9개

N == 2
10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98 => 17개

N이 2일때까지 나열했는데, 뭔가 느낌이 온다.

하나의 수(A)를 고정하면 그 뒤에 붙을 수 있는 숫자는 한정되어 있다.
만약 1로 끝나는 수라면 뒤에 0 또는 1.
2로 끝난다면 1 또는 3
1~8사이의 수는 두 가지 경우가 발생한다.
...

그리고 0과 9로 끝나는 경우는 한 가지 존재한다.
즉 K자리의 수를 만들기위해 K-1자리의 수를 만들고, 뒤에 P라는 숫자로 끝나는 경우가 몇가지 있는지 조사한다면, DP로 접근할 수 있다.

// dp[i][j] : 1의 자리가 j인 i자리 수를 만드는 경우의 수.
// j가 1~8이라면,
dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
// j가 0 또는 9 라면,
dp[i][0] = dp[i-1][1]
dp[i][9] = dp[i-1][8]

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static int N;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = stoi(in.readLine());

		int[][] dp = new int[101][10];
		for (int i = 1; i < 10; ++i)
			dp[1][i] = 1;

		for (int i = 2; i <= N; ++i) {
			dp[i][0] = dp[i-1][1];
			dp[i][9] = dp[i-1][8];
			for (int j = 1; j <= 8; ++j)
				dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
		}
		int sum = 0;
		for (int i = 0; i <= 9; ++i){
			sum += dp[N][i];
			sum = sum % 1000000000;
		}

		System.out.println(sum);
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}