Java : 계단오르기(Fibo : Memoization)

문제

풀이

• 이 문제는 계단을 한 칸씩 높게 올라갈 때 마다 규칙이 보여서 그걸 기반으로 해결했다.

  1칸은 1번
  2칸은 2번
  3칸은 3번
  4칸은 5번
  ...
  7칸은 21번

• 증가량을 보면 피보나치 수열이 보인다. 피보나치 n번째 + n-1번째의 합이 답이 나온다.
• 조건에는 최대 계단이 35칸까지 일반 피보나치 시간초과이므로 배열에 저장하면서 반환하는 메모이제이션을 사용한다.

잡담

• fibo(n) + fino(n-1) 이 답인 이유는 한 번에 3칸을 건너뛸 수 없기 때문에 아래 두 개의 값을 합한다.

전체 코드

package inflearn;

import java.util.Scanner;

public class I1001 {
  static int[] ch;

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    ch = new int[n + 1];

    fibo(n);
    System.out.println(ch[n] + ch[n - 1]);
  }

  static int fibo(int n) {
    if (ch[n] > 0) return ch[n];
    if (n <= 2) return ch[n] = 1;

    return ch[n] = fibo(n - 2) + fibo(n - 1);
  }
}