[코딩테스트][Java] 백준 10844, 쉬운 계단 수

문제

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

10844번: 쉬운 계단 수

 

접근

• 모든 인접한 숫자끼리의 차이가 1이라면 계단 수이다.
• 0으로 시작하는 계단수는 없다. (0, 01, 001 등)
• N이 주어질때 길이가 N인 계단수는 몇개인가

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

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

위의 식에서 N=2인 경우 N=1에서의 각각의 수(1,2,3,...,9)에서 ±1하여 일의 자리에 추가된 것을 볼 수 있습니다. 

위 그림을 기반으로 점화식을 다음과 같이 만들 수 있습니다.

dp[N][L] = dp[N-1][L-1] + dp[N-1][L+1] 
// 숫자의 길이가 N이고 마지막 수가 L일때의 계단수의 값

dp 배열에 저장되는 값들은 길이가 N이고 마지막 수가 L일때 가질수 있는 계단수의 값을 저장합니다. 예를 들어 dp[2][2]의 의미는 길이가 2이고 마지막 수가 2인 계단수의 값을 의미합니다. dp[2][2]가 가질수 있는 계단수들은 12, 32으로 총 2가지이므로 dp[2][2]=2입니다. N=2까지의 dp 배열은 다음과 같습니다.

위 그림을 통하여 주의할 점은 L=0인 경우와 L=9인 경우입니다.

• L = 0 : 마지막 수가 0이므로 앞의 자리에 +1한 1 만을 허용합니다. (ex 10)
• L = 9 : 마지막 수가 9이므로 앞의 자리에 -1한 8 만을 허용합니다. (ex 98)

L에 범위에 따른 dp의 점화식은 다음과 같습니다.

dp[N][L] = {
                dp[N-1][L+1], if L=0
                dp[N-1][L-1] + dp[N-1][L+1], if 1<=L<=8
                dp[N-1][L-1], if L=9
           }

 

소스코드

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


public class Main {
	public static long solution(int n)
	{
		long[][] dp = new long[n+1][10];
		final long DIVISOR = 1000000000;
		for(int j=1;j<=9;j++)
		{
			dp[1][j] = 1;
		}
		
		for(int i=2;i<=n;i++)
		{
			for(int j=0;j<=9;j++)
			{
				if(j==0)
				{
					dp[i][j] = dp[i-1][j+1] % DIVISOR;
				}
				else if(j>=1 && j<=8)
				{
					dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % DIVISOR;
				}
				else if(j==9)
				{
					dp[i][j] = dp[i-1][j-1] % DIVISOR;
				}
			}
		}
		
		long answer = 0;
		for(int j=0;j<=9;j++)
		{
			answer += dp[n][j];
		}
		
		return answer %DIVISOR;
	}
	
	public static void main(String args[]) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		long answer = solution(n);
		System.out.println(answer);
	}
}

 

References

https://mygumi.tistory.com/260