[Ch.10 - DP] 01. 계단오르기

1. 계단오르기

 

설명

철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는

1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다.

그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가?

입력

첫째 줄은 계단의 개수인 자연수 N(3≤N≤35)이 주어집니다.

출력

첫 번째 줄에 올라가는 방법의 수를 출력합니다.

예시 입력 1 

7

예시 출력 1

21

 

---

복잡한 문제의 경우

직관적으로 알 수 있는 단위인, 작은 문제들로 쪼갠 후, 확장을 하는 방식으로, 메모이제이션을 이용해 해결

-> DP (Dynamic Programming)

 

dy[7]=?

dy[1]=1
dy[2]=2

 

dy[3]은 dy[1]에서 혹은 dy[2]에서 오는 경우로 나뉜다.

dy[1]에서 오는 경우 1가지

dy[2]에서 오는 경우 2가지

dy[3]은 dy[1]+dy[2]로 3가지

 

dy[4]는 dy[2]에서 혹은 dy[3]에서 오는 경우로 나뉜다.

dy[2]에서 오는 경우 2가지

dy[3]에서 오는 경우 3가지

dy[4]는 dy[2]+dy[3]로 5가지

 

dy[5]는 dy[3]에서 혹은 dy[4]에서 오는 경우로 나뉜다.

dy[3]에서 오는 경우 3가지

dy[4]에서 오는 경우 5가지

dy[5]는 dy[3]+dy[4]로 8가지

 

dy[6]은 dy[4]에서 혹은 dy[5]에서 오는 경우로 나뉜다.

dy[4]에서 오는 경우 5가지

dy[5]에서 오는 경우 8가지

dy[6]는 dy[4]+dy[5]로 13가지

 

dy[7] dy[5]에서 혹은 dy[6]에서 오는 경우로 나뉜다.

dy[5]에서 오는 경우 8가지

dy[6]에서 오는 경우 13가지

dy[7]은 dy[5]+dy[6]으로 21가지

---

package dynamic.ch10;

import java.util.Scanner;
//계단오르기
//한칸 혹은 두칸씩
public class Dynamic01 {
	static int[] dy;
	static 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) {
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		dy=new int[n+1];
		System.out.print(solution(n));
	}

}