[백준/10844/Java] 쉬운계단수

 

문제링크

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

 

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

 

출력

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

 

 

풀이

점화식 규칙을 찾기 위하여 1부터 0까지 적어보겠습니다.

배열의 index에 해당하는 숫자로 끝나는 경우로 정리하면서 적어보도록 하겠습니다.

 

N=1, 즉 1자리인 경우

1자리인 경우 각 숫자만 존재합니다.

10번째 index는 0으로 끝나는 경우로 하였습니다.

 

N=2, 즉 2자리인 경우

배열의 index에 해당하는 숫자가 끝나도록 정리하고 보면 이렇게 됩니다.

2로 끝나는 경우를 보면 12, 32가 됩니다.

2 앞에 1이 있는 경우가 있고 2 앞에 3이 있는 경우가 있습니다.

N=1에서 앞에 있는 숫자를 가져온다고 하면 이렇게 됩니다.

선이 너무 많아지는 관계로 1, 3, 5, 7, 9로 끝나는 경우만 선을 표시하였습니다.

N=2일 때는 앞 자리가 1보다 작거나 1보다 클 수 밖에 없습니다.

 

N=3, 즉 3자리인 경우

3자리가 되는 경우를 정리하면 이렇게 됩니다.

2로 끝나는 경우를 보시면 D[2][1]이 21이므로 (앞자리) 21 + 2 (끝자리)가 됩니다.

그리고 2로 끝나는 경우 중 빨간 박스를 보시면 D[2][3]에서 가져와서

23 + 2

43 + 2가 됩니다.

지금까지 경우의 수가 어떻게 이루어지는 확인해보았습니다.

점화식 규칙은 D 배열을 2차원 배열로 생각하시면 쉽게 찾을 수 있습니다.

D[i][1] = D[i][2]
D[i][2] = D[i][1] + D[i][3]
D[i][3] = D[i][2] + D[i][4]
D[i][4] = D[i][3] + D[i][5]
D[i][5] = D[i][4] + D[i][6]
D[i][6] = D[i][5] + D[i][7]
D[i][7] = D[i][6] + D[i][8]
D[i][8] = D[i][7] + D[i][9]
D[i][9] = D[i][8] + D[i][10]
D[i][10] = D[i][9]

 

D[i][2]부터 D[i][9]까지 2번째 배열 인덱스를 j라고 하면 D[i][j] = D[i-1][j-1] + D[i-1][j+1]로 표현할 수 있습니다.
D[i][1]은 가장 좌측에 있으므로 j-1이 존재하지 않기 때문에 D[i][1] = D[i-1][2] = D[i-1][j+1]입니다.

D[i][10]은 가장 우측에 있으므로 j+1이 존재하지 않기 때문에 D[i][10] = D[i-1][9] = D[i-1][j-1]입니다.

 

N=10일 때까지 경우의 수를 표시하면 이렇게 됩니다.

D[1] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
D[2] = [1, 2, 2, 2, 2, 2, 2, 2, 1, 1]
D[3] = [2, 3, 4, 4, 4, 4, 4, 3, 3, 1]
D[4] = [3, 6, 7, 8, 8, 8, 7, 7, 4, 3]
D[5] = [6, 10, 14, 15, 16, 15, 15, 11, 10, 4]
D[6] = [10, 20, 25, 30, 30, 31, 26, 25, 15, 10]
D[7] = [20, 35, 50, 55, 61, 56, 56, 41, 35, 15]
D[8] = [35, 70, 90, 111, 111, 117, 97, 91, 56, 35]
D[9] = [70, 125, 181, 201, 228, 208, 208, 153, 126, 56]
D[10] = [125, 251, 326, 409, 409, 436, 361, 334, 209, 126]

 

저는 1, 2, 3, 4, 5, 6, 7, 8, 9, 0으로 생각해서 풀었지만

0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 해도 총합을 구하기 때문에 동일한 결과가 나옵니다.

생각하기 편하신 방향으로 하시면 됩니다.

 

 

소스

D[1][1~0]까지의 초기화를 잊지 말고 해주셔야 합니다. 실수하기 딱 좋죠.

그리고 D배열에 저장할 때마다 1,000,000,000으로 나눈 나머지를 저장하셔야 1,000,000,000이 넘지 않습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main
{
	static int N;
	static int D[][] = new int[101][11];

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

		N = Integer.parseInt(br.readLine());

		// d[1][10] = 0임
		for (int i = 1; i <= 9; i++)
		{
			D[1][i] = 1;
		}
		
		for (int i = 2; i <= N; i++)
		{
			for (int j = 1; j<=10 ; j++)
			{
				if (j == 1) D[i][j] = D[i-1][j+1];
				else if (j == 10) D[i][j] = D[i-1][j-1];
				else D[i][j] = D[i-1][j-1] + D[i-1][j+1];
				D[i][j] %= 1000000000;
			}
			
		}
		long answer = 0;
		for (int i = 1; i <= 10; i++)
		{
			answer += D[N][i];
		}
		System.out.println(answer % 1000000000);
		
//		for (int i = 1; i <= N; i++)
//		{
//			System.out.println("D[" + i + "] = " + Arrays.toString(D[i]));
//		}
	}
}