프로그래머스, 레벨3, 멀리띄기

레벨 3 멀리띄기 문제.

문제는 간단하다. 00이는 멀리띄기를 1칸 또는 2칸 할 수 있다.

자연수 n칸을 줄때 00이가 n까지 갈 수 있는 경우의 수를 구하라.

만약 4를 건네주면

1,1,1,1

1,2,1

2,1,1

1,12

2,2

로 총 5가지의 경우가 나온다

이런 문제는 당연히 DP로 접근을 해야하는데 지난번 풀었던 문제와는 살짝 다르다.

지난번 동전문제는 1,2,1 이나 2,1,1 이나 결국 같은 것으로 인식하지만 이 문제는 그렇지 않다.

하지만 지난번 거스름돈 문제를 풀면서 느낀점은 쪼개서 해결할 수 있다는 것이었고

이 문제 역시 쪼개서 풀도록 노력하였다.

이 문제를 1,2,3,4 의 숫자를 각각 경우의 수를 풀어쓰면 좀더 쉽게 이해 할 수 있다.

결국 4라는 숫자는 3에 1을 더한 경우와 2에 2를 더한 경우이기에

결국 4의 경우의 수는 3과 2의 경우의 수를 더한 것과 같고

이를 정리하게되면 피보나치 수열이 된다..

껄껄