[伯俊]10844号簡単な階段数/Java,Python


Baekjoon Online Judge


algorithm practice


問題をちくじ解く


15.動的計画法1


いくつかの基礎的な動的計画法の問題を解いてみましょう.
Java/Python

9.簡単な階段数


10844号
動的計画法を用いて階段数の問題を解く
  • Java
  • import java.io.BufferedReader;
    import java.io.InputStreamReader;
    import java.io.IOException;
     
    public class Main {
    	
    	final static long MOD = 1000000000;
    	
    	public static void main(String[] args) throws IOException {
    		
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    		
    		int N = Integer.parseInt(br.readLine());
    		
    		long[][] DP = new long[N + 1][10];
    		
    		// 첫 번째 자릿수는 오른쪽 맨 끝의 자릿수이므로 경우의 수가 1개
    		for(int i = 1; i < 10; i++) {
    			DP[1][i] = 1;    // DP 배열 초기 상태 
    		}
    		
    		// 2 ~ N 탐색
    		for(int i = 2; i <= N; i++) {
    			
    			for(int j = 0; j < 10; j++) {
    				
    				if(j == 0) {    // 끝이 0이면 1만 가능
    					DP[i][0] = DP[i - 1][1] % MOD;
    				}else if (j == 9) { // 9라면 8만 가능
    					DP[i][9] = DP[i - 1][8] % MOD;
    				}else {    // -1,+1
    					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);
    	}
     
    }
  • Python
  • import sys
    N = int(sys.stdin.readline())
    DP = [[0 for i in range(10)] for j in range(101)]
    mod = 1000000000
    for i in range(1, 10):
        DP[1][i] = 1
        
    for i in range(2, N + 1):
        for j in range(10):
            if j == 0:
                DP[i][j] = DP[i-1][1]
            elif j == 9:
                DP[i][j] = DP[i-1][8]
            else:
                DP[i][j] = DP[i-1][j-1] + DP[i-1][j+1]
    
    print(sum(DP[N]) % mod)