[코딩문제]계단 오르기 - 3 계단

 #include <iostream>

using namespace std;

/*

계단을 오르는 방법에는 여러가지가 있습니다. 

한 계단씩만 올라가는 방법이 있고, 

두 계단만 올라가는 방법이 있고 혹은 

세 계단만 올라가는 방법이 있습니다.

계단의 수를 n이라 하고

한번에 올라갈 수 있는 계단의 수를 최대 세 계단이라고 했을 때 

계단을 올라갈 수 있는 경우의 수를 구하시오.

*/

int Fibonacci(int n)

{

if (n == 1) return 1;

else if (n == 2) return 2;

else if (n == 3) return 4;

else if (n > 0)

{

int first = 1;

int second = 2;

int third = 4;

int temp = 0; //임시 변수

int count = n - 3; //반복을 돌릴 카운트

for (int i = 0; i < count; i++)

{

temp = first;

first = second;

second = third;

third += temp + first; //third = temp(first) + first(second) + third

}

return third;

}

else

{

return -1;

}

}

//메인함수

void main()

{

cout << Fibonacci(6) << endl;

getchar();

}

해설 : 

이런건 노트에 적어가면서 풀어보면 규칙이 보입니다.

계단이 하나일 경우 (1) 계단 만 오를 수 있으니 경우의 수는 1 입니다.

두개일 경우 (1, 1)로 오르거나 (2) 계단 오를 수 있어서 경우의 수가 2입니다.

계단이 세 개일 경우 (1, 1, 1)로 오르거나 (1, 2) 로 오르거나 (2, 1)로 오르거나 (3) 계단 전부 오를 수 있으므로 경우의 수는 4개 입니다.

계단이 네 개일 경우 (1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 2), (1, 3), (3, 1) 의 경우로 경우의 수는 7 입니다.

감이 좋으신 분들은 여기에서 눈치를 챘을 수 있습니다.

잘보면 보이는 규칙이 있습니다.

저는 계단 다섯 개 까지 경우의 수를 써보고 규칙을 찾아냈습니다.

1로 시작 할경우 바로 전 계단의 경우의 수와 동일한 경우나 나타납니다.

2로 시작 할 경우 바로 전전 계단의 수에서의 경우의 수가 나오고

3로 시작 할 경우 바로 전전전 계단의 수에서의 경우의 수가 나오는 것이 보입니다.

 

네 계단 에서의   (1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 2), (1, 3), (3, 1) 을 보기 좋게 나열해보면

 (1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 3)

 (2, 1, 1), (2, 2)

 (3, 1)

이고 첫 숫자들만 지워보면

 (1, 1, 1), (1, 2), (2, 1), (3)

 (1, 1), (2)

 (1)

이렇게 되고 이는 각각 세 계단일 경우, 두 계단일 경우, 하나의 계단일 경우 와 동일 합니다.

즉 앞의 숫자 3개를 더하면서 진행되는 피보나치 수열을 짜면 문제는 해결 되는 것입니다.

이해가 잘 안되시는 분들은 다섯, 여섯 계단 일 경우도 노트에 적어 보시면 이해가 되실 것 같습니다.

문제 출처 : 코딩도장(http://codingdojang.com/)

코딩 출처 : 내 머리, 내 손