[백준] 10844 쉬운 계단 수 java

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

 

풀이 과정

dp 파트가 약해서 정리해보고자 한다.

문제를 요약해 보자면 ' N자리 수가 있을 때, 인접한 모든 자릿수가 1씩 차이씩 나는 수가 몇 개인지 구하는 것'이다.

 

여기서 유의해야 할 점은 다음 두 가지를 조심해야 한다.

 

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

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

 

즉 10 다음에 붙을 수 있는 값은 1밖에 없으므로 101이 되는 것이고,

만약 19가 온다면 8밖에 올 수 없으므로 198이 되는 것이다.

그 외의 값 (2~8)은 각 값보다 -1 또는 +1 인 값을 가질 수 있다.

 

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

---

이는 다이나믹 프로그래밍을 사용하여 풀면 된다.

 

Top-Down 방식으로 재귀로 풀어내는 방법과

Bottom-Up 방식으로 반복문으로 풀어내는 방법이 있다.

 

 

 

정답 코드

[Top-Down]

재귀를 사용하여 점화식 그대로 적용하는 Top-Down 방식을 살펴보자면

 

자릿수를 표현할 변수인 digit

자릿값을 표현할 변수인 val로 둔다.

import java.util.*;
import java.io.*;

class Main
{
    static int N;
    static final int MOD = 1000000000;
    static int[][] dp;
	
    public static void main(String args[]) throws IOException 
    {
    	// 입력
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	dp = new int[N + 1][10];
    	
    	// 초기화
    	for(int i = 0; i < 10; i++) {
    		dp[1][i] = 1;
    	}
    	
    	// 실행  1~9까지 경우의 수 모두 더해줌
    	int res = 0;
    	for(int i = 1; i <= 9; i++) {
    		res += recur(N, i);
    		res %= MOD;
    	}
    	
    	// 결과
    	System.out.println(res % MOD);
    }
    
    static int recur(int digit, int val) {
    	
    	// 첫째 자릿수에 도착한다면 더이상 탐색할 필요 없음
    	if (digit == 1) {
    		return dp[digit][val];
    	}
    	
    	// 해당 자릿수의 val값에 대해 탐색하지 않았을 경우
    	if (dp[digit][val] == 0) {
    		// 이전 자리는 1밖에 못 옴 
    		if (val == 0) 
    			dp[digit][val] = recur(digit - 1, 1);
    		// 이전 자리는 8밖에 못 옴
    		else if (val == 9)
    			dp[digit][val] = recur(digit - 1, 8);
    		else 
    			dp[digit][val] = recur(digit - 1, val - 1) + recur(digit - 1, val + 1);
    	}
    	
    	return dp[digit][val] % MOD;
    }

}

 

 

[Bottom-Up]

반복문을 사용하여 dp를 적용한 풀이이다.

import java.util.*;
import java.io.*;

class Main
{
    static int N;
    static final int MOD = 1000000000;
    static int[][] dp;
	
    public static void main(String args[]) throws IOException 
    {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	dp = new int[N + 1][10];
    	
    	dynamic();
    	
    	int res = 0;
    	for(int i = 0; i < 10; i++) {
    		res = (res + dp[N][i]) % MOD;
    	}
    	
    	System.out.println(res);
    }
    
    static void dynamic() {
    	// 첫번재 자리수는 오른쪽 맨 끝의 자리수이므로 경우의수 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++) {
            	// 0이면 이전 자릿수의 1만 가능
    			if (j == 0) 
    				dp[i][0] = dp[i - 1][1];
                // 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];
    			
    			dp[i][j] %= MOD;
    		}
    	}
    }

}