섹션 10 Dynamic Programming - 2. 돌다리 건너기

문제 설명

철수는 개울을 건너기 위해 돌다리를 건너야 합니다.
돌은 1번부터 N번까지 번호가 매겨져 있고, 철수는 한 번에 한 칸 혹은 두 칸씩 이동할 수 있습니다.

즉, 1칸 or 2칸씩만 앞으로 이동할 수 있을 때 N개의 돌을 건너는 경우의 수는 몇 가지일까요?

이 문제는 대표적인 피보나치 수열 형태의 DP 문제입니다.

 

※ 반대편 땅은 N번째 돌 바로 다음 칸입니다. 즉, 도착 지점은 (N+1)번 칸입니다.

---

입력

• 자연수 N (3 ≤ N ≤ 35)
  (돌의 개수)

출력

• 철수가 개울을 건너는 모든 경우의 수

---

예시 입력

7

예시 출력

34

---

코드 구현

import java.util.Scanner;

public class Main {
    static int[] dy;

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

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

---

코드 설명 (DP + 피보나치 구조)

• dy[i]: i번째 돌에 도착하는 경우의 수
• 이동 조건이 1칸 또는 2칸이기 때문에 dy[i] = dy[i-1] + dy[i-2] 라는 점화식을 사용할 수 있습니다.
• 시작점에서 N번 돌을 건넌 후 N+1번 돌에 도착한다고 보고, dy[n + 1]을 정답으로 반환합니다.

---

시간 복잡도

• O(N) → 반복문 한 번으로 dy 배열을 채움

---

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

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

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