Baekjoon 10844 쉬운 계단 수 JAVA

10844번: 쉬운 계단 수

문제

45656이란 수를 보자.

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

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

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

출력

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

풀이

DP문제이다.

K는 자릿수라고 생각한다. 자리수는 최대 100까지 가능하다.

처음에 배열을 초기화 하는 방식은 0을 제외한 나머지 위치들을 1로 초기화 해준다. 문제의 조건에 따라 0으로 시작하는 수는 계단수가 아니기 때문이다.

그 뒤로 N만큼 반복하면서 temp배열에 이전에 있던 배열들에서 1을 더한 값과 1을 뺀 값들을 만들어준다.

모든 경우의 수로 값을 만들어 주었다면 값을 더하고 1,000,000,000으로 만든 나머지만 남긴다.

 

코드

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt(),ans=0;
		int[] num=new int[10], temp;
		
		for(int i=1;i<=9;i++)
			num[i]=1;
		
		for(int k=1;k<n;k++) {
			temp = new int[10];
			for(int i=0;i<=9;i++) {
				if(i-1>=0)
					temp[i-1]+=num[i];
				if(i+1<=9)
					temp[i+1]+=num[i];
			}
			for(int i=0;i<=9;i++) {
				num[i]=temp[i]%1000000000;
			}
		}
		for(int i=0;i<10;i++)
			ans=(ans+num[i])%1000000000;
		System.out.println(ans);
	}
}