[인프런 자바/java] 1. 계단오르기 _디버깅의 눈물

 

 

 

체크 포인트

 

1. 다이나믹 프로그래밍(Dynamic Programming, 동적계획법)을 이용

-큰 문제를 여러 가지 작은 문제로 나누어 해결해보는 DP를 이용했다.

-예를 들어, 

 

1계단을 오르는 경우의 수 = 1

2계단을 오르는 경우의 수 = 2

 

를 구한 후,

3계단을 오르는 경우의 수는 1계단에서 오는 경우와 2계단에서 오는 경우의 합인 것을 통해 해결했다.

1계단에서 2칸을 오르거나, 2계단에서 1칸을 오르면 3계단에 오를 수 있기 때문이다.

 

이를 통해 

 

N계단을 오르는 경우의 수 = N-1계단을 오르는 경우의 수 + N-2계단을 오르는 경우의 수

 

임을 추론할 수 있었다.

 

 

2. Top-down(탑다운) 방식, Bottom-up(바텀업) 방식

-다이나믹 프로그래밍에는 크게 1)Top-down(탑다운) 방식과 2)Bottom-up(바텀업) 방식이 존재한다.

 

1)Top-down(탑다운)은 가장 큰 문제를 방문한 후, 작은 문제를 찾아가는 방식이고, 재귀를 통해 구현한다.

2)Bottom-up(바텀업)은 가장 작은 문제를 방문 후, 큰 문제를 찾아가는 방식이고, 반복문(for문)을 통해 구현한다.

 

 

 

 

풀이

1)Top-down(탑다운) 방식 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public  class Main {
	
	// 동적 계획법 활용 배열
	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(3≤N≤35)
    	int N = Integer.parseInt(st.nextToken());
    	
    	//    N  1 2 3 4 5  6  7
    	// dp[N] 1 2 3 5 8 14 21
    	
    	// 배열 초기화
    	dp = new int[N+1];
    	// 1계단을 오르는 경우의 수
    	dp[1] = 1;
    	// 2계단을 오르는 경우의 수
    	dp[2] = 2;
    	
    	System.out.println(solution(N));
    	
    } // end of Main
    
    
    
    
    static int solution(int N) {
    	
    	// 이전에 구해놓은 dp[N] 값이 있다면,
    	if(dp[N]!= 0){
    		// 그 값을 return;
    		return dp[N];
    	}
    	// 이전에 구해놓은 값이 없다면, 구하자!
    	else{
    		// dp[N]은 
    		// (1)1계단 이전에서 오는 경우와
    		// (2)2계단 이전에서 오는 경우의 합과 같다.
    		// 계단을 이동하는 것은 1칸과 2칸 이동이 전부이기 때문!
    		dp[N] = solution(N-1) + solution(N-2);
    		
    	}
    	
    	// 구한 dp[N]값을 return 해준다.
    	return dp[N];
    	
    } // end of solution

} // end of Main

 

 

1)Botton-up(바텀업) 방식 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public  class Main {
	
	// 동적 계획법 활용 배열
	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(3≤N≤35)
    	int N = Integer.parseInt(st.nextToken());
    	
    	//    N  1 2 3 4 5  6  7
    	// dp[N] 1 2 3 5 8 14 21
    	
    	// 배열 초기화
    	dp = new int[N+1];
    	// 1계단을 오르는 경우의 수
    	dp[1] = 1;
    	// 2계단을 오르는 경우의 수
    	dp[2] = 2;
    	
    	System.out.println(solution(N));
    	
    } // end of Main
    
    
    
    
    static int solution(int N) {
    	
    	// bottom-up(바텀업)방식
		for(int i=3; i<=N; i++){
			dp[i] = dp[i-1] + dp[i-2];
		}
		
    	
    	// 구한 dp[N]값을 return 해준다.
    	return dp[N];
    	
    } // end of solution

} // end of Main