1, 2 또는 3 단계를 사용하여 n 번째 계단에 도달하는 방법 계산

난이도 쉽게
자주 묻는 질문 아마존 코드네이션 GE 헬스 케어 Microsoft 문 프로그 연구소 페이팔 동네 짱
조합 동적 프로그래밍조회수 32

"1, 2 또는 3 단계를 사용하여 n 번째 계단에 도달하는 방법을 세는 방법"문제는 사용자가지면에 서 있다는 것을 나타냅니다. 이제 계단 끝에 도달해야합니다. 1, 2, 3 단계 만 점프 할 수 있다면 끝까지 도달 할 수있는 방법은 얼마나 될까요?

1, 2 또는 3 단계를 사용하여 n 번째 계단에 도달하는 방법 계산

2
2

설명

지상에서 직접 2 단계에 도달하거나 먼저 2 층에 도달 한 후 앞으로 이동하기 때문에 두 가지 방법이 있습니다.

접근

문제는 우리가 지상에서 시작하도록 계단 끝에 도달하는 총 다른 수의 방법을 묻습니다. 따라서 계단에는 2 개의 계단이 있습니다. 그런 다음 두 가지 가능한 방법이 있습니다. 바로 2 단계로 이동하거나 2 단계에서 1 단계로 이동 한 다음 2 단계로 이동하는 것입니다. 마찬가지로, 1, 2 또는 3 단계를 사용하여 n 번째 계단에 도달하는 방법을 계산해야합니다.

순진한 접근 방식은 가능한 모든 방법을 생성 한 다음 계산하는 것입니다. 그러나이 접근 방식은 시간이 많이 걸립니다. 따라서 시간 복잡성을 줄이려면 몇 가지 다른 방법을 생각해야합니다. 순진한 접근 방식에서 논의한 방법은 재귀 0 단계부터 시작할 수있는 솔루션입니다. 그런 다음 각 재귀 호출에서 i + 1, i + 2 및 i + 3 단계로 이동합니다. n 번째 단계에 도달하면 카운터를 증가시킵니다. 이렇게하면 카운터는 n 번째 단계에 도달하는 방법의 수를 저장합니다. 그러나이 단계는 동일한 문제를 반복해서 재 계산합니다. 따라서이 솔루션을 최적화하기 위해 동적 프로그래밍.

동적 프로그래밍 솔루션에서 우리는 i 번째 단계에 있다고 생각합니다. 그러면 i 번째 단계에 도달하는 방법의 수는 i-1 단계, i-2 단계 또는 i-3 단계입니다. 그래서 공식적으로 말하면,이 재귀 공식을 사용하여 방법 [i] = 방법 [i-1] + 방법 [i-2] + 방법 [i-3]. 우리는 우리의 문제를 해결할 것입니다.

암호

1, 2 또는 3 단계를 사용하여 n 번째 계단에 도달하는 방법을 계산하는 C ++ 코드

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;cin>>n;
    int dp[n+1];
    // base case
    dp[0] = 1;
    for(int i=1;i<=n;i++){
        dp[i] = ((i-1)>=0 ? dp[i-1] : 0) +
                ((i-2)>=0 ? dp[i-2] : 0) +
                ((i-3)>=0 ? dp[i-3] : 0);
    }
    cout<<dp[n];
}
5
13

1, 2 또는 3 단계를 사용하여 n 번째 계단에 도달하는 방법을 계산하는 Java 코드

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
  int n = sc.nextInt();
    int dp[] = new int[n+1];
    // base case
    dp[0] = 1;
    for(int i=1;i<=n;i++){
        dp[i] = ((i-1)>=0 ? dp[i-1] : 0) +
                ((i-2)>=0 ? dp[i-2] : 0) +
                ((i-3)>=0 ? dp[i-3] : 0);
    }

    System.out.print(dp[n]);
  }
}
5
13

복잡성 분석

시간 복잡성

의 위에), n 번째 단계까지 루프를 실행해야하기 때문입니다. 따라서 동적 프로그래밍 측면에서 0에서 n까지의 단일 상태가 있었고 전환 비용은 O (1)입니다. 따라서 시간 복잡도는 선형입니다.

공간 복잡성

의 위에), 1D DP 배열을 만들어야하기 때문입니다. 솔루션의 공간 복잡성은 선형입니다.

Translate »