[10844번] 쉬운 계단 수 JAVA☕

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

알고리즘 [접근 방법]

문제 설명을 보면 일단 자릿수가 100, 즉 100째자리 수까지 주어지니 기본 형식은 long타입으로 해준다고 가정하고 설명하겠다. 또한 문제에서 가장 중요한 포인트는 '인접한 모든 자릿수가 1씩 차이가 난다'는 것이 포인트.

여기서 유의해야 할 점이 있는데 다음 두 가지를 조심해야 한다.

1) N번째 자릿수의 자릿값이 0인 경우 : 다음 자릿수의 자릿값은 1밖에 올 수 없다.
2) N번째 자릿수의 자릿값이 9인 경우 : 다음 자릿수의 자릿값은 8밖에 올 수 없다.

즉, 10 다음에 붙을 수 있는 수는 1밖에 없으므로 101 이 되는 것이고, 만약 19가 온다면 8밖에 올 수 없으므로 198 이 되는 것이다. 그 외의 값(2~8)은 각 값보다 -1 또는 +1 인 값을 가질 수 있다.

 

그럼 자릿값은 0~9를 가질 수 있고, N개의 자릿값을 표현해야하므로 2차원 배열이 필요하다.

// N자릿수에 각각의 자릿값(0~9)를 의미
Long[] dp = new Long[N + 1][10]

(자릿수는 배열의 경우 0부터 시작하기 때문에 N+1)

 

[Top-Down]

재귀를 쓰기 위해 두 가지 변수를 둘 것인데, 자릿값을 표현 할 변수인 digit, 자릿값을 표현 할 변수인 val, 이렇게 두 개를 이용 할 것이다.

 

그리고 재귀호출은 자릿값에 따라 자릿값이 0이라면 다음에 올 자릿값은 1로, 9라면 8로 호출해주고, 그 외의 경우는 val-1, val+1 둘 다 가능하니 둘 다 호출하여 경우의 수를 합하면 된다.

 

/*
 digit 는 자릿수, val은 자릿값을 의미함
	 
 첫째 자리수는 각 val이 끝이기 때문에
 경우의 수는 1밖에 없다. 즉, dp[1]의 각 자릿값은
 1로 초기화 되어있어야한다.
*/
	
static long recur(int digit, int val) {		
 
	// 첫째 자리수에 도착한다면 더이상 탐색할 필요 없음
	if(digit == 1) {
		return dp[digit][val];
	}
			
	// 해당 자리수의 val값에 대해 탐색하지 않았을 경우 
	if(dp[digit][val] == null) {
		// val이 0일경우 다음은 1밖에 못옴
		if(val == 0) {
			dp[digit][val] = recur(digit - 1 ,1);
		}
		// val이 1일경우 다음은 8밖에 못옴
		else if(val== 9) {
			dp[digit][val] = recur(digit - 1, 8);
		}
		// 그 외의 경우는 val-1과 val+1 값의 경우의 수를 합한 경우의 수가 됨
		else {
			dp[digit][val] = recur(digit - 1, val - 1) + recur(digit - 1, val + 1);
		}
	}
	return dp[digit][val];
}

dp[1][0], dp[1][1], ⋯ ,dp[1][9] 는 1로 초기화 되어있어야 한다.

recur라는 함수를 탐색할 때, digit 번째 자릿수의 자릿값 val에 대하여 해당 자릿수의 경우의 수가 없는, 즉 dp[digit][val]이 null 인 경우 자릿값에 따라 3가지 경우로 나누어 digit-1번째 자릿수로 재귀호출을 해준다.

 

쉽게 말하면 N 번째 자릿수의 자릿값이 없으면 N-1번째 자릿수를 탐색하고, N-1 도 없으면 N-1의 -1 번째 자릿수를 탐색하여 값이 있을 때 까지 찾아나가는 방식인 것이다.

 

[Bottom-Up]

long[][] dp = new long[N + 1][10];
		
// 첫 번째 자릿수는 오른쪽 맨 끝의 자릿수이므로 경우의 수가 1개밖에 없음 
for(int i = 1; i < 10; i++) {
	dp[1][i] = 1; 
}
		
// 두 번째 자릿수부터 N까지 탐색 
for(int i = 2; i <= N; i++) {
			
	// i번째 자릿수의 자릿값들을 탐색 (0~9) 
	for(int j = 0; j < 10; j++) {
				
		// j=0, 즉 자릿값이 0이라면 이전 자릿수의 첫번째 자릿수만 가능 
		if(j == 0) {
			dp[i][0] = dp[i - 1][1];
		}
		// j=9라면 이전 자릿수는 8만 가능
		else if (j == 9) {
			dp[i][9] = dp[i - 1][8];
		}
		// 그 외의 경우 이전 자릿수의 자릿값 +1, -1 의 합이 됨 
		else {
			dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]);
		}
	}
}

엄연히 하면 자릿수가 거꾸로 되어있는데, 어차피 경우의 수를 구하는 것이기 때문에 크게 문제되진 않는다.

풀이 및 코드

- 방법 1 : [Scanner + Top-Down]

import java.util.Scanner;
 
public class Main {
	
	static Long[][] dp;
	static int N;
	final static long MOD = 1000000000;
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		N = in.nextInt();
		dp = new Long[N + 1][10];
		
		// 첫번째 자릿수는 1로 초기화 
		for(int i = 0; i < 10; i++) {
			dp[1][i] = 1L;
		}
		
		long result = 0;
		
		// 마지막 자릿수인 1~9까지의 경우의 수를 모두 더해준다.
		for(int i = 1; i <= 9; i++) {
			result += recur(N, i);
		}
		System.out.println(result % MOD);
	}
	
	/*
	 dist 는 자릿수, val은 자릿값을 의미함
	 
	 첫째 자리수는 각 val이 끝이기 때문에
	 경우의 수는 1밖에 없다. 즉, dp[1]의 각 자릿값은
	 1로 초기화 되어있어야한다.
	*/
	
	static long recur(int digit, int val) {		
 
		// 첫째 자리수에 도착한다면 더이상 탐색할 필요 없음
		if(digit == 1) {
			return dp[digit][val];
		}
			
		// 해당 자리수의 val값에 대해 탐색하지 않았을 경우 
		if(dp[digit][val] == null) {
			// val이 0일경우 다음은 1밖에 못옴
			if(val == 0) {
				dp[digit][val] = recur(digit - 1 ,1);
			}
			// val이 1일경우 다음은 8밖에 못옴
			else if(val== 9) {
				dp[digit][val] = recur(digit - 1, 8);
			}
			// 그 외의 경우는 val-1과 val+1 값의 경우의 수를 합한 경우의 수가 됨
			else {
				dp[digit][val] = recur(digit - 1, val - 1) + recur(digit - 1, val + 1);
			}
		}
		return dp[digit][val] % MOD;
	}
}

참고로 MOD는 10억으로 초기화 되어있고, 분명히 문제에서 '10억으로 나눈 나머지 값'을 출력하라고 했다. N이 최대 100, 즉 자릿수만 100자리라 경우의 수일지라도 long타입을 벗어날 수 있다. 때문에 long 범위에서 벗어나지 않도록 각 return마다 나머지값을 return시켜주어야 한다.

 

- 방법 2 : [Scanner + Bottom-Up]

import java.util.Scanner;
 
public class Main {
 
	final static long mod = 1000000000;
    
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		
		long[][] dp = new long[N + 1][10];
		
		// 첫 번째 자릿수는 오른쪽 맨 끝의 자릿수이므로 경우의 수가 1개밖에 없음 
		for(int i = 1; i < 10; i++) {
			dp[1][i] = 1; 
		}
		
		// 두 번째 자릿수부터 N까지 탐색 
		for(int i = 2; i <= N; i++) {
			
			// i번째 자릿수의 자릿값들을 탐색 (0~9) 
			for(int j = 0; j < 10; j++) {
				
				// j=0, 즉 자릿값이 0이라면 이전 자릿수의 첫번째 자릿수만 가능 
				if(j == 0) {
					dp[i][0] = dp[i - 1][1] % mod;
				}
				// j=9라면 이전 자릿수는 8만 가능
				else if (j == 9) {
					dp[i][9] = dp[i - 1][8] % mod;
				}
				// 그 외의 경우 이전 자릿수의 자릿값 +1, -1 의 합이 됨 
				else {
					dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;
				}
			}
		}
		
		long result = 0;
		
		// 각 자릿값마다의 경우의 수를 모두 더해준다. 
		for(int i = 0; i < 10; i++) {
			result += dp[N][i];
		}
		
		System.out.println(result % mod);
	}
 
}