문제를 보자 눈앞이 깜깜해졌다..

 

경우의 수 구하기 비슷한 것인데, 어떻게 result 를 구할 수 있을지 막막했다.

 

그래서 일단 예시를 늘려 보았다.

 

칸이 1칸일 때 = 1칸 = 1

칸이 2칸일 때 = 1칸, 1칸 // 2칸 = 2

칸이 3칸일 때 = 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칸 = 5  

칸이 5칸일 때 = 1/1/1/1/1 + 1/1/1/2 + 1/1/2/1 + 1/2/1/1 + 1/2/2 + 2/1/1/1 + 2/1/2 + 2/2/1 = 8

 

어렴풋이 문제를 보고 n 을 구하기 위해선 n-1 에 무언가를 더해야 할 것 같다 정도 느낌이 있었는데, 

저렇게 result 값을 나열해 놓고 보니 어느정도 확신이 생긴다. 

 

이것은 얼마전 풀이했던 피보나치 수열에 해당한다 !

 

즉 , n = n-1 + n-2  라는 것

 

 

 

n이 1 or 2 여도 정상적인 answer 가 출력되게 살짝 손을 봤다.

 

answer  는 잊지 말고 위의 사항을 적용해 준다.

 

(return 값에만 적용할 경우, for문 과정에서 int한계를 넘어가는 경우가 생긴다) 

 

+ Recent posts