<Algorithm> 54. 2579번 계단 오르기

1. 2579번 계단 오르기

• DP문제, 처음에는 DFS로 접근하였는데 시간초과가 발생하였다. 최대의 계단이 300개 인데 이때 수많은 경우가 발생한다. 

• 문제에 주어진 조건을 자세히 확인한다음 경우의 수가 얼마나 발생하는지 보고 DP인지 다른 알고리즘인지 판단하는게 좋을 것 같다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
 
public class Main {
    
    static int max = Integer.MIN_VALUE;
    static int[] dp = new int[1000001];
    static int[] dp2 = new int[1000001];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()) + 1;
        int arr[] = new int[N];
        for(int i = 1 ; i < N; i ++) {
            arr[i] =  Integer.parseInt(br.readLine());
        }
        
        dp[0] = 0;
        dp[1] = arr[1];
        dp[2] = arr[1] + arr[2];
        
        
        for(int i = 3; i < arr.length ; i++) {
            dp[i] = Math.max(dp[i-3] + arr[i-1] + arr[i], dp[i-2] + arr[i]);
            // 2칸을 뛰어넘어서 바로 도착하는 경우와  2칸을 뛰고 한칸을 오는 경우 중 최대값을 입력한다.
        }
        
        System.out.println(dp[arr.length-1]);
        
    }
    
    public static void dfs(int[] arr, int count, int index, int total) {
        int[] d = {1, 2};
        
        if(index == arr.length - 1) { 
            if(max < total) max = total;
            return;
        }
        
        
        if(count == 2) {
            if(index + 2 < arr.length) {
                total += arr[index + 2];
                dfs(arr, 1 , index + 2, total);
                total -= arr[index + 2];
                // 백트래킹 
            }
            return;
        }
        
        
        for(int i = 0; i < 2; i ++) {
                
            int nIndex = index + d[i];
            
            if(nIndex < arr.length && count < 2) {
                if(i == 0) {
                    total += arr[nIndex]; 
                    dfs(arr, count + 1, nIndex,total);
                    total -= arr[nIndex];
                }
                else {
                    total += arr[nIndex];
                    dfs(arr, 1, nIndex, total);
                    total -= arr[nIndex];
                }
            }
            
        }        
        
    }
    
}