[백준] 10844번 : 쉬운 계단 수

문제

 

 

접근 방식

문제 자체는 간단한데 어떻게 풀어야 할지 어려웠던 문제였지만

일단 규칙을 찾아야 할 거 같아서 수들을 적다 보니 특징을 발견해서 풀 수 있었다.

1	10	101
2	12	121 123
3	21	210 212
4	23	232 234
5	32	
6	34
7	43
8	45
9	54	(생략)
	56
	65
	67
	76
	78	787 789
	87	876 878
	89	898
	98	987 989

 

각각 한 자리부터 세 자리까지의 쉬운 계단 수를 나열한 목록인데

0과 9로 끝나는 부분만 제외한 모든 수들이 2배씩 늘어나고

0과 9로 끝나는 경우만 그대로 하나인 것을 알 수 있다.

 

0으로 끝나는 경우에는 09가 될 수 없으니 01만 올 수 있고

9로 끝나는 경우도 마찬가지로 90이 될 수 없으니 98만 올 수 있다.

 

0과 9를 제외한 1~8로 끝나는 수들은 전부 자기 자신 - 1, 자기 자신 + 1

이렇게 두 가지로 늘어날 수 있기 때문에 이 특징들을 이용해 계산해 주면 된다.

 

우선 DP 테이블은 각 자릿수별로 특정 숫자로 끝나는 가짓수를 기록하기 위해

다음과 같이 2차원 배열로 정의했다.

dp[n][10] = 1 ~ n번째 자리수의 0 ~ 9로 끝나는 경우의 수

 

이제 위에서 정리한 쉬운 계단 수의 특징들을 가지고 테이블을 채워주면 되는데

0과 9의 경우는 기존 가짓수를 그대로 따라가기 때문에

d[i][0] = d[i-1][1]
d[i][9] = d[i-1][8]

 

위와 같이 이전 값을 그대로 기록해주면 된다.

 

각각 이전 자리수의 0번과 9번 값을 가져오지 않고 1번과 8번을 가져오는 이유는

이전 자리수가 1인 경우에만 10처럼 0으로 끝날 수 있고

이전 자리수가 8인 경우에만 89처럼 9로 끝날 수 있기 때문이다.

d[i][j] = d[i-1][j-1] + d[i-1][j+1]

 

2 ~ 8의 경우에는 이전 자릿수의 j-1과 j+1인 경우에 j가 될 수 있으니

두 값을 모두 더해주면 된다.

 

풀이

public class Main {

	private static final int MOD = 1_000_000_000;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		byte n = Byte.parseByte(br.readLine());

		long[][] dp = new long[n + 1][10];

		dp[1] = new long[]{0, 1, 1, 1, 1, 1, 1, 1, 1, 1};

		for (byte i = 2; i <= n; i++) {
			dp[i][0] = dp[i - 1][1] % MOD;
			dp[i][9] = dp[i - 1][8] % MOD;
			for (byte j = 1; j < 9; j++) {
				dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;
			}
		}

		long count = 0;

		for (byte i = 0; i < 10; i++) {
			count += dp[n][i];
		}

		System.out.println(count % MOD);
	}
}