[DP] 1. 계단오르기

<<풀이>>

 

dp: 앞에 구한 값을 메모제이션으로 저장해두고 이를 이용해요 다음 단계에서 이용하는 방식이다.

그 중에서도 밑에서 올라가는 방식을 bottom-up 방법이다.

 

내가 DFS 방식과 헷갈렸었는데, 이 문제를 보고 와닿는다. DFS는 아예 재귀함수로 완전 깊이 아래까지 갔다가 오는 거라면 dp 같은 경우는 이미 이전의 값을 저장해두고 바로 활용하는 차이점이 있다. 그래서 dfs가 메모제이션을 활용하더라도 dp보다는 시간이 많이 걸리는 것이다. 

import java.util.Scanner;

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 - 2] + dy[i - 1];
        }
        return dy[n];
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        dy = new int[n + 1];
        System.out.println(T.solution(n));
    }
}

 

 

아직 dp에 대해 정확하게 안다고는 할 수 없다고 생각한다. 문제를 여러개 더 풀어보면서 내 것으로 만들자 !!