[2] 멀리 뛰기 (메모이제이션, 피보나치)

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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 이하인 정수입니다.

---

키포인트

ㄴ 방법들 가지수를 직접 나열하면 피보나치 수열로 이루어져 있다는 것을 알 수 있다.

ㄴ 괜히 어렵게 접근하지 말고 처음에는 몇번 직접 가지수를 체크해가며 규칙을 추론해보자

ㄴ 메모이제이션 dp 로 풀면 된다

// n의 개수
// 1인 경우
// ㄴ 1 => 1
// 2: 11 2 => 2
// 3: 111 21 12 => 3
// 4: 1111 22 211 112 121 => 5
// 5: 11111 2111 1211 1121 1112 221 122 212 => 8
// 6: 111111 222 2211 2112 1122 1212 2121 1221 21111 12111 11211 11121 11112 => 13
// 7: 1111111 (4개)2221 (10개)22111 (6개)211111 => 21개
// n칸 가는 방법 가지수 -> (n-2) + (n-1)
// dp로 풀면 된다

#include <string>

using namespace std;

long long solution(int n) {
	long long answer = 0;
	int* arr = new int[n + 1];
	arr[0] = 1;
	arr[1] = 1;
	arr[2] = 2;
	for (int i = 3; i <= n; i++)
		arr[i] = (arr[i - 2] + arr[i - 1]) % 1234567;

	answer = arr[n];
	delete[] arr;
	return answer;
}

 

오답노트

ㄴ 처음에는 피보나치를 발견 못하고 순열과 조합을 이용해 풀려했다.

// n개의 집합에서 k개를 구하는 경우의 수를 이용해서 풀려 했다.

// n: 2와 1로 이루어진 집합에서

// k: 2의 개수를 구하는 경우의 수

// 그러나 이렇게 하면 n! 값을 구하는 부분에서 버퍼오버플로우 때문에 답을 구할 수 없게 된다.

#include <string>
#include <vector>

using namespace std;

int f(int n, int k)
{
	if (n == k)
		return 1;
	else if (k == 1)
		return n;
	else
		return f(n, k - 1) * (n - k + 1) / k;

}

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

	// 한 번에 1칸 or 2칸
	// 5인 경우 2일 수 있는 경우의 수가 2번, 
	// 11111, 2111, 221
	// => 1 + 4C1 + 3C2 
	// => 1 + 4 + 3 => 8

	int val = n / 2; // 2의 최대 개수 카운트
	for (long long i = 0; i <= val; i++)
	{
		// 1의 개수
		//(n - i * 2);
		// 2의 개수
		//i;
		// 전체 개수
		//n - i;
		// 구할 값
		// (n - i)Ci
		// => n - i를 i개수 만큼
		if (i == 0)
			answer++;
		else
		{
			answer += f(n-i, i);
		}
	}

	return answer % 1234567;
}