[프로그래머스] - 멀리 뛰기(C++)

멀리 뛰기

 

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

 

제한사항

• n은 1 이상, 2000 이하인 정수입니다.

 

입출력 예

n	result
4	5
3	3

 

입출력 예 설명

 

입출력 예 #1
위에서 설명한 내용과 같습니다.

입출력 예 #2
(2칸, 1칸)
(1칸, 2칸)
(1칸, 1칸, 1칸)
총 3가지 방법으로 멀리 뛸 수 있습니다.

 

시작 코드

#include <string>
#include <vector>

using namespace std;

long long solution(int n) {
    long long answer = 0;
    return answer;
}

 

나의 풀이

#include <vector>

using namespace std;

long long solution(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;

    long long first = 1, second = 2, current;

    for (int i = 3; i <= n; i++)
    {
        current = (first + second) % 1234567;
        first = second;
        second = current;
    }

    return second;
}

 

코드 분석

n이 1일때와 2일때 1과 2를 리턴하도록 하고, first와 second를 1, 2로 생성하고 current 변수를 생성합니다. for문을 3부터 시작하여 n까지 돌리면서 current에 first와 second를 더한값을 1234567로 나눈 나머지를 넣도록 합니다. 이후 first에는 second 값을 넣고 second에는 current값을 넣어줍니다. 최종적으로 second값을 리턴합니다.

 

풀이 설명

문제가 원하는 것은 n칸을 가기위해 1칸 혹은 2칸씩 움직여서 도달하는 경우의 수의 개수를 구하는 것입니다. 앞에 if문은 n이 1과 2로 주어졌을 때는 어차피 1과 2가 답이기 때문에 제외시키기 위해 작성되었습니다. 그리고 first와 second를 통해 주어진 n에 대한 경우의 수를 도출하는데, 이는 피보나치 수열, DP의 원리와 흡사합니다. DP의 원리를 적용하는 이유는 모든 계산 결과를 가지고 계산을 진행하지 않고 이전에 사용된 두 값을 통해서 최종적인 값에 도달할 수 있는 메모리제이션의 특성이 있기 때문입니다.

 

시간복잡도 : O(n)

공간복잡도 : O(1)

 

실행결과

 

<NEXT>

이번에는 정답률 70%의 연습문제 "멀리 뛰기" 문제를 다뤄보았습니다. 다음에는 "N개의 최소공배수" 문제를 살펴보도록 하겠습니다. 감사합니다.