섹션 10 Dynamic Programming - 1. 계단오르기

설명

철수는 계단을 오를 때 한 번에 한 칸 또는 두 칸을 오를 수 있다.
총 N계단이 주어졌을 때 철수가 정상까지 올라갈 수 있는 방법의 수를 구하자.

---

입력

• 자연수 N (3 ≤ N ≤ 35)

출력

• 철수가 정상까지 올라갈 수 있는 경우의 수

---

예시 입력

7

예시 출력

21

---

해결 방법

• 철수가 n번째 계단에 도달하는 경우는 다음 두 가지 경우에서 올 수 있다:
  • (n-1)번째에서 1칸 올라옴
  • (n-2)번째에서 2칸 올라옴
• 따라서 점화식: dy[n] = dy[n-1] + dy[n-2]
• 피보나치 수열과 동일한 구조

---

코드 구현

import java.util.*;

public class Main {
    static int[] dy;

    public int solution(int n) {
        dy[1] = 1;
        dy[2] = 2;
        for (int i = 3; i <= n; i++) {
            dy[i] = dy[i - 1] + dy[i - 2];
        }
        return dy[n];
    }

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

---

코드 설명 요약

• dy[i]: i번째 계단까지 오르는 방법의 수
• dy[1] = 1, dy[2] = 2는 초기값 (한 칸, 두 칸)
• 점화식대로 for문으로 누적 계산
• dy[n]에 정답 저장

---

시간 복잡도

• O(N) → 반복문 한 번만 수행하며 dy 배열을 채움

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런