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

1. 문제이해

https://programmers.co.kr/learn/courses/30/lessons/12914

코딩테스트 연습 - 멀리 뛰기

 

멀리뛰기를 할 때, 효진이는 한번에 1 또는 2칸만 뛸 수 있다.

멀리뛰기에 사용될 칸의 수 N이 주어질 때,

효진이가 뛸 수 있는 방법의 수는 몇가지인지 구하는 것이 목표이다.

 

 

 

2. 문제풀이

 

효진이가 뛰어야되는 칸의 수 N이 주어지고, 효진이는 한번에 1 또는 2칸만 뛸 수 있다.

이 때, 효진이가 뛸 수 있는 방법의 수를 구하는 것이 목표인데,

이 말은 즉, N이라는 수를 1과 2의 합으로 나타낼 수 있는 경우의 수를 구하는 것과 마찬가지이다.

 

예전 포스팅에서 주어진 수 N을 1, 2, 3의 합으로 표현할 수 있는 가짓수를 구하는

알고리즘을 구현한 적이 있었는데,

위 방법과 원리가 동일하다. (해당 포스팅은 아래 링크를 참고하자)

 

https://beginnerdeveloper-lit.tistory.com/44

[C++] 백준 9095번 1, 2, 3 더하기

 

 

1부터 5까지의 숫자를 1, 2의 합으로 나타내어 보면 다음과 같은 결과를 얻을 수 있다.

 

그림을 보면 알 수 있듯이, 숫자가 커질수록 다음과 같은 규칙이 나타난다.

 

1. N번째 경우의 수 = (N - 1번째 경우의 수 ) + (N - 2번째 경우의 수)

2. N번째 각 경우의 수 = (N-1 번째 경우의 수) + 1 또는 (N - 2번째 경우의 수) + 2

 

1번의 경우에서 볼 수 있듯, N번째 숫자를 1과 2의 합으로 나타낼 수 있는 경우의 수는

N - 1번째 경우의 수와 N - 2번째 경우의 수를 합한 것과 같다.

(2번의 경우에는 이번 문제풀이에서 중요한 부분은 아니다.)

 

무언가와 비슷하지 않은가? 바로 피보나치 수열과 비슷하다.

피보나치 수열은 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열인데,
이 문제의 경우에도 첫, 둘째 항이 1인것만을 제외하면,

 모든 항이 바로 앞 두항의 합이라는 것이 피보나치 수열과 동일하다.

 

피보나치 수열은 예전에 다뤄본 적이 있는데,

자세한 내용은 아래 포스팅을 참조하자.

(풀이 방법이 거의 동일하다.)

 

https://beginnerdeveloper-lit.tistory.com/53

[C++] 프로그래머스 피보나치 수

 

필자는 이 문제를  피보나치 수 때와 마찬가지로 2가지 경우로 풀이했는데,

하나는 재귀함수를 이용한 방법, 하나는 for문을 이용한 방법이다.

재귀함수를 이용한 방법은 프로그래머스에서는 시간초과가 발생했다.

따라서, for문을 이용해 시간초과를 해결해주었다.

(for문보다는 재귀함수가 더 시간이 오래걸리는 듯 하다.)

아래 소스코드 부분에는 두 가지 경우 모두 적어놓았다.

 

주어진 틀은 다음과 같았다.

 

 

 

 

3. 소스코드

1. 재귀를 통해 구현한 코드 (시간초과(실패))

#include <string>
#include <vector>

using namespace std;

long long numofcase(long long n) {
    if (n == 1) { // 정수가 1인 경우 
        return 1; 
    } 
    else if (n == 2) { // 정수가 2인 경우
        return 2; 
    }
    else if (n == 3) { // 정수가 3인 경우 
        return 3; 
    } 
    // 정수 N을 1, 2의 합으로 나타낼 수 있는 경우의 수는
    // (N-1)의 경우의 수 + (N-2)의 경우의 수
    else {
    	return numofcase(n - 1) + numofcase(n - 2);
    }
}

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

재귀를 통해 구현한 코드는 위와 같다.

numofcase라는 함수를 생성하고, 인자 n을 받아 n이 1, 2, 3인 경우에 따라 다른 값을 반환한다.

그 외의 경우에는 재귀를 통해 이전 두 경우의 값의 합을 반환한다.

해당 경우에는 프로그래머스에서 시간초과가 발생했다.

 

 

2. for문을 통해 구현한 코드 (성공)

#include <string>
#include <vector>

using namespace std;

long long solution(int n) {
    long long answer = 0;
    long long numofcase[2000];
    
    numofcase[0] = 0;	// 정수가 0인 경우
    numofcase[1] = 1;	// 정수가 1인 경우
    numofcase[2] = 2;	// 정수가 2인 경우
    
    for(int i = 3; i <= n; i++) { 
        numofcase[i] = (numofcase[i-1] + numofcase[i-2]) % 1234567; 
    }
    
    answer = numofcase[n];

    return answer;
}

for문을 이용해 구현한 코드이다.

numofcase라는 배열을 선언한 후, 해당 배열의 0, 1, 2의 값을 미리 대입해주고,

(3의 경우에도 1과 2의 경우의 합과 같으므로 따로 대입해주지 않았다.)

for문을 통해 3부터 n까지의 경우의 수의 합을 구하고, n번째 경우의 수를 구해주었다.

 

 

---

규칙만 잘 파악하면, 피보나치 수열 문제와 동일하게 풀이할 수 있는 문제였다.

예전에 피보나치 수 문제도, 1, 2, 3 더하기 문제도 모두 풀어보아서

비교적 쉽게 풀이할 수 있었던 문제였다.😊

예전에 풀어본게 지금와서 딱 떠오르고 도움이 된다니 뭔가 기쁘고 뿌듯하기도 하다!