[백준 알고리즘 풀이] 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));
    }
  }
  
}

No comments:

Post a Comment

무한의 세계

무한 집합의 크기 Cardinality , 즉 원소의 개수를 수학에서는 '농도'라고 말한다. 유한 집합의 크기는 그대로 원소의 개수 이지만, 무한 집합의 경우는 원소의 개수를 낱낱이 셈하는 것은 불가능하기 때문에 '농도'라...