계단 오르기

04 Jun 2023 in Algorithm on Java, Coding, Test

문제

설명

철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는

1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다.

그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가?

입력

첫째 줄은 계단의 개수인 자연수 N(3≤N≤35)이 주어집니다.

출력

첫 번째 줄에 올라가는 방법의 수를 출력합니다.

예시 입력 1

7

예시 출력 1

21

해결방법

• 문제의 본질은 그대로 두되, 아주 작은 문제로 변환하는 것 → 다이나믹.
• 작은 문제에서 나온 정답으로 점점 사이즈 업 하면서 그 답을 활용 → Bottom-Up 방식

코드

import java.util.*;

class Main {
  static int[] dy;

  public int solution(int n) {
    dy[1] = 1; // 1번 계단 올라가는 경우의 수
    dy[2] = 2; // 2번 계단 올라가는 경우의 수
    // 3번 계단 올라가는 경우의 수? 
    // 1->2->3 , 1->3 , 2->3 = 3 (1+2)
    // 4번 계단 올라가는 경우의 수?
    // 1->2->3->4 , 1->2->4 , 1->3->4 , 2->3->4 , 2->4 = 5 (2+3)
    // 문제를 패턴화 할 수 있다. 여기서는 현재 계단 까지 오는 경우의 수 = 현재 계단 - 2 까지 오는 경우의 수 + 현재계단 -1 까지 오는 경우의 수
    for (int i = 3; i <= n; i++) dy[i] = dy[i - 2] + dy[i - 1];
    return dy[n];
  }

  public static void main(String[] args) {
    Main T = new Main();
    Scanner kb = new Scanner(System.in);
    int n = kb.nextInt();
    dy = new int[n + 1];
    System.out.print(T.solution(n));
  }
}