프로그래머스 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

입출력 예 #2

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

---

문제 풀이

 

이 문제는 f(n) = f(n-1) + f(n-2) 이라는 규칙을 볼 수 있다.

 

▼f(3)일 때

f(1)	1칸
f(2)		2칸	1칸, 1칸
f(3)	1칸, 2칸	2칸, 1칸	1칸, 1칸, 1칸

 

▼f(4)일 때

f(2)	2칸		1칸, 1칸
f(3)		2칸, 1칸		1칸, 2칸	1칸, 1칸, 1칸
f(4)	2칸, 2칸	2칸, 1칸, 1칸	1칸, 1칸, 2칸	1칸, 2칸, 1칸	1칸, 1칸, 1칸, 1칸

 

위 표들을 보면 f(n)은 f(n-2)의 경우의 수에 2칸을 더한 것과, f(n-1)의 경우의 수에 1칸을 더한 것의 합인 것을 알 수 있다.

 

재귀함수로 풀게 된다면 큰 수를 계산할 땐 시간이 많이 걸릴 것이다. 최적화 면에서 반복문을 활용하는게 좋다.

long long solution(int n) {
    long long answer = 0;
    int n1 = 1, n2 = 2;	

    if(n <= 2) answer = n;
    for(int i = 3; i<=n; i++){
        answer = (n1 + n2) % 1234567;    
        n1 = n2;
        n2 = answer;
    }
    
    return answer;
}

위처럼 작성 시 시간 복잡도는 O(n)이고, 상수 개수만 사용해 공간 복잡도는 O(1)이다.

 

int longJump(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    return longJump(n - 1) + longJump(n - 2);
}

long long solution(int n) {
    return longJump(n) % 1234567;
}

재귀함수 사용 시 시간 복잡도 O(2^n), 공간 복잡도 O(n)로 시간 초과가 발생한다.

 

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

    int dp[n];
    
    dp[1] = 1;
    dp[2] = 2;

    for (int i = 3; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567;
    }

    return dp[n];
}

배열 사용 시 시간 복잡도 O(n)이지만 배열 유지면에서 공간 복잡도가 O(n)이 된다.

 

 

 

 

 

출처: 프로그래머스 코딩 테스트 연습, 

https://school.programmers.co.kr/learn/challenges