BJ_S1_10844_쉬운계단수 - Java

[문제링크]

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

10844번: 쉬운 계단 수

---

[문제]

45656이란 수를 보자.

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

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

---

[입력]

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

---

[출력]

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

---

[예제 입력 1]

1

---

[예제 출력 1]

9

---

[예제 입력 2]

2

---

[예제 출력 2]

17

---

[설명]

이 문제는 DP 문제이다. Long으로 선언하는 것의 주의하고 풀면 된다.

1. DP를 2차원 배열로 선언한다.

2. DP[1]은 1~9까지 총 1씩 입력해준다.

3. DP[2]부터는 양 옆의 숫자에 해당하는 DP를 더해주면 된다. (단, 0일때는 1일때의 값만 가져오고, 9일때는 8일때의 값만 가져온다.) 

 

 

백준 알고리즘 10844번 JAVA풀이

 

import java.util.Scanner;

public class Main {

	static long mod=1000000000;
	public static void main(String[] args) {
		Scanner scann = new Scanner(System.in);
		int N=scann.nextInt();
		long[][] dp = new long[N+1][10];
		for(int i=1;i<10;i++) {
			dp[1][i]=1;
		}
		for(int i=2;i<=N;i++) {
			for(int j=0;j<10;j++) {
				if(j==0) {
					dp[i][0]=dp[i-1][1]%mod;
				} else if(j==9) {
					dp[i][9]=dp[i-1][8]%mod;
				} else {
					dp[i][j] = (dp[i-1][j-1]+dp[i-1][j+1])%mod;
				}
			}
		}
		long answer=0;
		for(int i=0;i<10;i++) {
			answer+=dp[N][i];
		}
		System.out.println(answer%mod);
	}
}

 

 

 

궁금하신 부분이나 부족한 점은 댓글로 알려주시면 감사하겠습니다.