멀리 뛰기 – 수열 알고리즘

문제

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는

(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)

5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 출력하는 jumpCase 함수를 완성하세요. 예를 들어 4가 입력된다면, 5를 반환해 주면 됩니다.

풀이

1부터 경우의 수를 구해나가다 보면 규칙성을 찾을 수 있다.

개적화로 그럴싸한 코드를 만들 수 있지만 제출용 코드는 위와 같았다.

경우의 수를 따져보면 아래와 같다.

n    	1    2    3    4    5    6    …
answer	1    2    3    5    8    13    …

그냥 3부터는 이전 수와 그 이전수의 합으로 구성된다. 피보나치수열

쉽게 생각해보면 이런 방식이다.

효진이는 1칸 또는 2칸밖에 뛰지 못한다.

6칸을 기준으로 볼 때 6칸을 뛰기 위해서는 5칸까지 뛴 다음 1칸을 뛰던지 또는 4칸까지 뛴 다음 2칸을 뛰면 된다.

따라서 총 뛰어야 되는 칸(x) = (x-1)까지 경우 + (x-2)까지의 경우인 것이다.

이러한 방식을 Dynamic Programming(동적 계획법)이라 한다. 풀고자 하는 하나의 거대한 알고리즘을 나누고 나눠 구하기 쉬운 작은 단위들로 변경하고 그 작은 단위들을 종합하여 거대한 알고리즘을 풀이하는 것이다.

소스 코드

#include <iostream>
#include <vector>

using namespace std;

int jumpCase(int n)
{
  int answer = 0;

  vector<int> ary;
  for (int i = 1; i <= n; i++)
  {
    if (i == 1)
      ary.push_back(i);
    else if (i == 2)
      ary.push_back(i);
    else
      ary.push_back(ary[i - 3] + ary[i - 2]);
  }
  answer = ary[n - 1];

  return answer;
}
int main()
{
  int test = 4;

  cout << jumpCase(test);
}

아래 코드는 다른 사람의 풀이인데 풀이가 깔끔해서 첨부한다. 재귀함수를 이용하셨다

#include <iostream>

using namespace std;

int jumpCase(int num)
{
  return num < 2 ? 1 : jumpCase(num - 2) + jumpCase(num - 1);
}
int main()
{
  int test = 4;

  cout << jumpCase(test);
}

출처

알고리즘 연습 Level 3 | 프로그래머스