Algorithm - Climbing Stairs

• 2024-02-14 에 풀이한 문제

• 총 풀이시간 0935 ~ 0958

  • 문제 분석 ( 0935 ~ 0944 )
  • 손 코딩 ( 0945 ~ 0949 )
  • 슈도코드 [ 원초적 설계 -> 알고리즘 ] ( 0950 ~ 0953 )
  • 코드 구현 ( 0954 ~ 0958 )

• 나의 풀이 깃허브 : 풀이 클릭!

알고리즘 문제(Java) : 계단오르기 ( Dynamic )

1. 문제

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

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

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

2. 입력

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

3. 출력

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

4. 문제 풀이

• 복잡도로 따지면 굉장히 큰 문제가 있을 떄, 이 문제의 본질은 변하지 않고 작은 단위의 문제로 바꾸어 푸는 방법을 사용한다.

• 예를들어 계단이 20개면, 그걸 직관적으로 알 수 있는 계단 1개로 소형화 시켜서 푸는 것이다.

• 그리고 그 다음 소형화한 계단을 풀고 해서, 순차적으로 푸는 것이다.

• 즉, 큰 문제는 한 번에 직관적으로 보기 어려우니, 그걸 한 번에 푸는게 아닌, 직관적으로 볼 수 있을만큼 문제를 소형화 해서 여러번 푸는 방법을 다이나믹 방법이라고 한다.

• 이 문제를 예시로 보면

  • 계단이 1개일 때는, 1 == 1가지 방법

  • 계단이 2개일 때는 1+1 혹은 2 == 2가지 방법

  • 이걸 배열에 담는다. dy[1] = 1 , dy[2] = 2

  • 자, 그럼 계단이 3개일 때는 ?? 1, 2번째 계단을 오는 방법에서 넘어 오는 것이기 때문에 1+2 해서 3이된다.

  • 계단이 4개일 때는 2, 3 번째 계단을 오는 방법에서 넘어 오는 것이기 때문에 2+3 해서 5가 된다.

  • 즉, 피보나치 수열 관계임을 알 수 있다.

  • 그렇게 해서 N 개일 때의 방법의 갯수를 구할 수 있다.

public class Climbing_Stairs {
    public static int solution(int n) {
        int[] arr = new int[n+1];
        arr[1] = 1;
        arr[2] = 2;
        for ( int i=3; i<=n; i++ ) {
            arr[i] = arr[i-1] + arr[i-2];
        }
        return arr[n];
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        System.out.println(solution(n));
    }
}