[백준 알고리즘 풀이] 2579번 계단 오르기

전형적인 동적 계획법으로 recursive와 memoization 기법을 활용했다. 한 계단 또는 두 계단이기 때문에 n - 1, n - 2 모든 경우의 트리에서 최대값을 출력하도록 구현한다.

import java.util.Scanner;

/*
 * 2579번 계단 오르기
 */
public class Main {
 
  static int[] x;
  static int[] memo;
 
  public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
 
    x = new int[n + 1];
    memo = new int[n + 1];
    for (int i = 1; i <= n; i++) {
      x[i] = sc.nextInt();
    }
 
    System.out.println(f(n, 2));
    sc.close();
  }
 
  private static int f(int n, int t) {
    if (n == 0)
      return x[0];
    if (n == 1) {
      if (t == 1) {
        return x[1];
      } else {
        return x[1] + x[0];
      }
    }
    if (t == 1) {
      if(memo[n] > 0)
        return memo[n];
          
      return memo[n] = x[n] + f(n - 2, 2);
    } else {
      return x[n] + Math.max(f(n - 1, 1), f(n - 2, 2));
    }
  }
  
}