키큰개발자

문제링크 : http://codeup.kr/problem.php?id=3704

해결 방법 :

n 이 5라면은 다음과 같이 총 13가지 경우의 수를 알 수 있다.

5=1+1+1+1+1

5=1+1+1+2

5=1+1+2+1

5=1+2+1+1

5=2+1+1+1

5=1+1+3

5=1+3+1

5=3+1+1

5=1+2+2

5=2+1+2

5=2+2+1

5=2+3

5=3+2

이걸 보고 생각해보면 5를 도달하기 직전 시점에서 보면 한 칸 전에오는 경우의수 가 있을 것이고, 두 칸 전에 오는 경우의 수도 있을거고 그리고 세 칸전에 오는 경우의 수가 있을것이다.

그렇다면 n에 도달하는데 모든 경우의 수는 n-1까지 오는데 경우의수 + n-2 까지 오는데 경우의 수 + n-3 까지 오는데 경우의수로 모든 경우를 다 합해주면은 원하는 답을 구할 수 있다.

이렇게하면 정답은 구할수 있지만, 이렇게 모든 경우를 세주면은 하나의 경우에있어서 계속 3가지의 경우의수가 발생이 되므로 3의 n승이라는 어마어마한 시간이 걸려서 틀리게 된다.

따라서, 중복되는 경우를 세주지 않게하기위해서 memo라는 배열에 n에 도달하는 경우의수를 미리 기록해둔다.

그렇게되면 일단 n이 1씩계속 감소하며 모든경우를 구하게 되고 n-2, n-3으로 부르는 재귀함수는 n-1의 재귀함수에 모두 포함되므로 경우의수가 확 줄어들게 된다. 

이제 코드를 작성해 보면 다음과 같다.