[Level 3] 멀리 뛰기 (jumpCase)

• 안녕하세요 BlockDMask 입니다.

• 오늘은 Level 3 멀리뛰기 를 풀어봤습니다.

• let's get it

0. 제목

• Programmers Level 3 멀리 뛰기

• Programmers Level 3 JumpCase

1. 문제설명

• 멀리뛰기를 연습하는 학생이 있는데

• 한번에 1칸 또는 2칸을 뛸수 있습니다.

• 예를 들어 칸이 4개 있을때.
  1칸 1칸 1칸 1칸
  1칸 2칸 1칸
  2칸 1칸 1칸
  1칸 1칸 2칸
  2칸 2칸
  으로 갈 수 있다.

• 총 5가지 방법.

• 이런식으로 칸의 수 n 이 주어질 때.

• 끝에 도달하는 방법이 몇가지 인지 출력하는 jumpcase 함수를 완성하시오.

2. 풀이과정

• 딱 문제를 보자마자

• DP (Dynamic Programming) 가 생각 났습니다.

• 작은것에서 큰것으로 가는 bottom up 방식으로 풀면 됩니다.
  칸이 1개 일때 (1)
  칸이 2개 일때 (1, 1), (2) 
  칸이 3개 일때 (1, 1, 1) (2, 1) (1, 2)
  을 배열로 저장을 합니다.

• tmp[0] = 1

• tmp[1] = 2

• tmp[3] = tmp[0] + tmp[1] 을 통해서

• tmp[n] = tmp[n-1] + tmp[n-2] 임을 알 수 있습니다.

3. 코드

#include<iostream>
#include<vector>
using namespace std;
 
//1칸이나 2칸만 이동할 수 있다
//Dynamic Programming
 
int tmp[1000001];
int jumpCase(int n)
{
    int answer = 0;
 
    tmp[0] = 1;
    tmp[1] = 2;
    for(int i=2; i<n; i++){
        tmp[i] = tmp[i-2] + tmp[i-1];
    }
 
    answer = tmp[n-1];
    return answer;
}
 
int main()
{
    int test = 4;
 
//아래는 테스트로 출력해 보기 위한 코드입니다.
    cout << jumpCase(test);
}
 

4. 인증

출처 : https://programmers.co.kr/learn/challenge_codes/153

감사합니다. 도움이되셨다면 하트 한번 부탁드립니다.