[C]BOJ 9095, 1, 2, 3 더하기

 

 

 

이 문제는 DP(Dynamic Programing)문제이다. 큰 문제를 작은 문제로 쪼개어 푸는 문제,, 피보나치 함수가 대표적인 예시이다. 우선 규칙을 찾아야한다.

 

문제에 대한 함수를 f(n)이라고 했을때, f(1)은 1이고, f(2)는 2이고, f(3)은 4이다. f(4) = 7이고 f(5)는 13이다. 여기서 규칙을 알 수 있다. f(n) = f(n-1) + f(n-2) + f(n-3) 으로 이루어진다. 따라서 제일 큰 입력값인 f(11)은 f(10)+f(9)+f(8) 으로 이루어질 것이다.

 

배열을 이용한 재귀

 

 

단순 재귀 코드

단순 재귀(아래 주석 코드)로 돌리면 아마 시간초과가 날 것이다. 제출을 해보지는 않았는데.. 그리고 실행도 안 해봤는데 아마 맞지않을까 아무튼. f(7)을 실행할때 f(6), f(5), f(4)를 계산할텐데, 나중에 f(11)을 입력받으면 다시 또 f(10), ... f(6), f(5), f(4) 를 계산하니까 비효율적이다. 그래서 배열을 만들고 값을 미리 저장해두었다가 필요할때 꺼내쓴다. 처음에는 계산이 안 되었다는 의미로 배열을 0으로 초기화해줬다.(main에서) 그리고 1,2,3 은 값을 그냥 주고 f(4)부터는 필요에 의해 계산하고, 값을 저장하도록 구현했다.