<알고리즘 문제풀이&연습>/[C++] 프로그래머스

[Level 3] 멀리 뛰기 (jumpCase)

사용자 BlockDMask 2017. 9. 14. 23:52
반응형
  • 안녕하세요 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. 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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);
}
 
cs


4. 인증



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

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



반응형