Lv2_[멀리뛰기, C++] 풀이 및 알고리즘 정리 - 프로그래머스

 

프로그래머스

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

---

멀리뛰기

먼저 n의 따른 방법의 수를 구해보자.

 

• n=1일 때, 1가지 방법
  • (1칸)
• n=2일 때, 2가지 방법
  • (1칸, 1칸)
  • (2칸)
• n=3일 때, 3가지 방법
  • (1칸, 1칸, 1칸)
  • (2칸, 1칸)
  • (1칸, 2칸)
• n=4일 때, 5가지 방법
  • (1칸, 1칸, 1칸, 1칸)
  • (2칸, 1칸, 1칸)
  • (1칸, 2칸, 1칸)
  • (1칸, 1칸, 2칸)
  • (2칸, 2칸)
• n=5일 때, 8가지 방법
  • (1칸, 1칸, 1칸, 1칸, 1칸)
  • (2칸, 1칸, 1칸, 1칸)
  • (1칸, 2칸, 1칸, 1칸)
  • (1칸, 1칸, 2칸, 1칸)
  • (1칸, 1칸, 1칸, 2칸)
  • (2칸, 2칸, 1칸)
  • (2칸, 1칸, 2칸)
  • (1칸, 2칸, 2칸)
• n=6일 때, 13가지 방법
  • (1칸, 1칸, 1칸, 1칸, 1칸, 1칸)
  • (2칸, 1칸, 1칸, 1칸, 1칸)
  • (1칸, 2칸, 1칸, 1칸, 1칸)
  • (1칸, 1칸, 2칸, 1칸, 1칸)
  • (1칸, 1칸, 1칸, 2칸, 1칸)
  • (1칸, 1칸, 1칸, 1칸, 2칸)
  • (2칸, 2칸, 1칸, 1칸)
  • (2칸, 1칸, 2칸, 1칸)
  • (2칸, 1칸, 1칸, 2칸)
  • (1칸, 2칸, 1칸, 2칸)
  • (1칸, 1칸, 2칸, 2칸)
  • (1칸, 2칸, 2칸, 1칸)
  • (2칸, 2칸, 2칸)

위의 n에 따른 방법의 개수가 증가하는 규칙을 보면, 1 2 3 5 8 13 으로 "피보나치 수열"이 떠오를 것입니다.

그러면 

• n=7일 때, 21가지 방법
• n=8일 때, 34가지 방법

n번째 수까지 손 쉽게 구할 수 있습니다.

피보나치 수열을 구하는 반복문을 n번째까지 구현하면 알고리즘은 완료됩니다.

아래는 작성한 코드입니다.

 

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
long long solution(int n) {
    long long answer = 0;
 
    vector<long long> tmp;
    tmp.reserve(n);
    tmp.push_back(1);
    tmp.push_back(2);
 
    for(int i = 2; i < n; i++) {
        tmp[i] = (tmp[i-1] % 1234567) + (tmp[i-2] % 1234567);
    }
    answer = tmp[n-1];
 
    return (answer % 1234567);
}