Select Working Days 배열에는 그날 벌 수 있는 돈들이 저장. 최대로 일해서 벌수있는 돈의 총합 구하기. 연속으로 일하는 것은 불가능. 순서 정하기 : 첫째날부터 x날까지 순서대로. (뒤쪽의 일이 앞쪽의 일에 영향을 주지 않기 때문에 순서를 이렇게 정할 수 있다.) a[x] : x일에 벌 수 있는 돈 D[x] : x일 까지 최대로 많이 벌 수 있는 돈의 총합. 집합 나누기 : D[x] 는 다음과 같이 쪼갤 수 있다. 1. x일에 일하는 경우 ⇒ 연속으로 일하면 안되므로 D[x-1]에서 일하지 않는 경우 + a[x] 2. x일에 일하지 않는 경우 ⇒ D[x-1]에서 일하는 경우 혹은 일하지 않는 경우에서 최댓값이 답 이 두 케이스중 최대가 D[x] 이다. 그리고 D[x]에서 일하는 경우는 D..

Fibonacci Number HTML 삽입 미리보기할 수 없는 소스 Recursion int F(int n) { if(n < 2) return 1; return F(n-1) + F(n-2); } 1부터 F(n) 까지의 합 만큼의 시간이 걸린다. 내부에서 이미 계산했던 함수들이 여러번 호출되기 때문. * 개선하는 방법 1. 재귀 sol 2. 재활용 찾기 ⇒ Memoization 3. 순서정하기 ⇒ DP Dynamic Programming int FF[1000]; int F(int n) { FF[0] = FF[1] = 1; for(i=2; i