인프런, 자바(Java) 알고리즘 문제풀이
Dynamic Programming - 1001. 계단 오르기
🗒️ 문제
🎈 나의 풀이
private static int solution(int n) {
int[] arr = new int[n];
arr[0] = 1;
arr[1] = 2;
for(int i=2; i<n; i++) {
arr[i] = arr[i-2] + arr[i-1];
}
return arr[n-1];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(solution(n));
}🖍️ 강의 풀이
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 kb = new Scanner(System.in);
int n=kb.nextInt();
dy=new int[n+1];
System.out.print(T.solution(n));
}💬 짚어가기
해당 문제는 그래프의 Dynamic Programming(동적 계획법)을 통해 풀 수 있다.
Dyanamic Programming이란
복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 부분 문제 반복과
최적 부분 구조를 가진 알고리즘을 일반적인 방식 보다 짧은 시간 내에 풀 수 있다.
풀이에서는 우선 오를 수 있는 계단의 크기만 큼 배열을 생성하였다. 해당 배열을 통해
낮은 계단(작은 문제)부터 접근하여 높은 계단(복잡한 문제)을 풀어나갈 수 있다.
계단을 오르는 방식으로 한번에 한 칸을 오르는 경우 또는 한번에 두 칸을 오르는 경우의
두 가지 방식이 있다. 따라서 첫 번째 계단과 두 번째 계단을 오르는 경우를 살펴보면,
✔️ 첫 번째 계단에 오르는 방법
▶︎ 바닥에서 계단 한 칸을 오른다.
✔️ 두번 째 계단에 오르는 방법
▶︎ 바닥에서 계단 한 칸씩 두번 오른다.
▶︎ 바닥에서 계단 두 칸을 한번에 오른다.
그럼 이제 세번 째 계단에 오를 수 있는 방법을 살펴보겠다.
✔️ 세번 째 계단에 오르는 방법
▶︎ 한 계단 밑에서 한 칸을 오른다.
▶︎ 두 계단 밑에서 계단 두 칸을 한번에 오른다.
즉, n 번 째 계단에 오르는 방법(경로)은 n-1번째 계단과 n-2 번째 계단에서 출발하여
오르는 두 경우 밖에 없다. 따라서 n-1 번째의 계단까지 오르는 모든 경우의 수와 n-2 번째
계단까지 오르는 모든 경우의 수의 합이, n 번 째 계단까지 오르는 모든 경우의 수 이다.
이를 코드로 구현하면 dy[i]=dy[i-2]+dy[i-1]이며, 피보나치 수열 형태와 동일하다.
