[Programmers] 멀리 뛰기

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

프로그래머스

 

---

 

문제 해결 과정

착안

한 번에 뛸 수 있는 칸의 수가 1 또는 2이므로, $n$ 번째 칸에 도달하기 위해서는 $(n-2)$ 번째 칸에서 2 칸을 뛰거나 $(n-1)$ 번째 칸에서 1 칸을 뛰어야한다. 따라서 $n$ 번째 칸에 도달하기 위한 경우의 수를 $f(n)$이라고 하면 $f(n)$은 아래와 같은 점화식(recursive formula)을 만족하며 처음 두 개의 항을 1, 2로 하는 피보나치 수열(Fibonacci sequence)이다.

 

$$f(n) = f(n-2) + f(n-1) \space \space \space (n > 2)$$

$$f(1) = 1, \space f(2) = 2$$

 

구현

동적계획법(dynamic programming)을 활용해 피보나치 수열의 $n$ 번째 항을 구하여 해결하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

using namespace std;

long long solution(int n)
{
	if (n < 3)
		return n;

	long long answer = 0;
		
	int a = 1, b = 2;
	for (int i = 2; i < n; i++)
	{
		answer = (a + b) % 1234567;
		a = b;
		b = answer;
	}
	
	return answer;
}

 

실행 결과