동적 계획 알고리즘 -(1)

📍 섹션10. DP (동적 계획 알고리즘)

동적 계획 알고리즘 -(1)

🟪 동적 계획(DP) 알고리즘

• 문제를 부분 문제로 나누어서, 가장 작은 부분문제로부터 해를 구한 뒤, 부분해를 이용하여 점차 상위 문제의 최적해를 구한다.

10-1. 계단 오르기

-피보나치 수열과 유사하다.

앞의 두 계단 가짓 수 합이 세 번쨰 가짓 수 가 되기 때문

규칙성을 찾자 ***

import java.util.Scanner;

/* 10-1. 계단 오르기 */
public class Main3 {
    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-2]+dy[i-1];//앞 두계단 합이 현재 계단 
        }
        return dy[n];
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main3 T = new Main3();
        Scanner kb = new Scanner(System.in);
        int n= kb.nextInt();
        dy = new int[n+1];
        System.out.println(T.solution(n));
    }
}

---

10-2. 돌다리 건너기

• 얘도 마찬가지로 피보나치 수열과 유사하다
• 다만 도착 지점은 돌다리를 모두 건너고 난 뒤 n+1지점이므로 유의할 것

import java.util.Scanner;

/* 10-2. 돌다리 건너기 */
public class Main4 {
    static int[] dy;
    //solution
    public int solution(int n) {
        dy[1]=1;
        dy[2]=2;
        for(int i=3; i<=n+1; i++) {
            dy[i]= dy[i-2]+dy[i-1];
        }
        return dy[n+1];
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main4 T = new Main4();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        dy= new int[n+2];
        System.out.println(T.solution(n));
    }
}

---