[백준_10844번] 쉬운 계단 수

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

10844번: 쉬운 계단 수

[문제]

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

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

 

[입력 조건]

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

 

[코드]

import java.util.*;

public class BaekJoon_10844 {
	public static int n;
	public static long[][] dp;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		dp=new long[n+1][10];
		long sum=0;
		
		// 입력받은 n에 대하여 각 끝 자리수 마다 나올 수 있는 개수를 모두 더한다.
		for(int i=1;i<=9;i++)
			sum+=easystair(n,i);
		
		System.out.println(sum%1000000000);
	}
	
	/*
	 * n이 늘어날수록 직전 n의 계단 수에 영향을 받는다. 
	 * 길이가 n이고 끝자리가 k인 계단수의 개수를 dp[n][k]라고 한다면
	 * dp[n][k] = 길이가 n-1이고 끝자리가 k-1 + 길이가 n-1이고 끝자리가 k+1 
	 * 즉, d[n][k] = d[n-1][k-1] + d[n-1][k+1]이다.
	 * 단, 끝자리가 9인 경우에는 8밖에 선택할 수 없고, 
	 * 끝자리가 0인 경우에는 1 선택할 수 없는 경우는 따로 처리해줘야 한다. 
	 */
	public static long easystair(int n, int k) {
		if(dp[n][k]==0) {
			// 자릿수가 1인 경우는 모든 개수가 1
			if(n==1)
				return 1;
			// 끝자리가 0인 경우는 1만 선택 가능
			if(k==0)
				dp[n][k]=easystair(n-1,1);
			// 끝자리가 9인 경우는 8만 선택 가능
			else if(k==9)
				dp[n][k]=easystair(n-1,8);
			else
				dp[n][k]=easystair(n-1,k-1)+easystair(n-1,k+1);
		}
		return dp[n][k]%1000000000;
	}
}

 

[고찰]

 동적 계획법 문제는 규칙을 찾아야 하는 문제가 많은 만큼 결과물에서 규칙적인 패턴을 발견하는 것이 중요한 것 같다. 이번 문제는 규칙을 찾기 어려워 다른 사람들의 아이디어에서 힌트를 얻어 해결하였다.

 길이가 n인 계단 수는 직전 계단수에 영향을 받으며, 직전 계단 개수로 값이 도출된다. 이때 끝자리가 0이나 9인 경우는 따로 처리해주는 것 까지 고려해야 완벽한 코드를 짤 수 있다. 나 스스로는 이러한 아이디어를 내지 못했다. 하지만 이렇게 규칙성을 찾는 문제는 경우의 수를 더 나열해보거나 표를 그려 패턴을 찾는 것이 좋다고 느꼈다.