다이나믹 단원 폼

ㅇㅇㅇ 문제

- 

문제요약

 

해결 방법

1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다.
- D[N] = "N개를 모두 구매하며 지불할 수 있는 최대 금액"

 

2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다.
- 정수 N이 주어지고, 앞에 어떤 조합이 존재하고 마지막 조합에서 아래와 같은 방법 중 1가지를 선택할 수 있다.

 

3. 다이나믹 프로그래밍 방법을 적용할 수 있는 문제인지 확인 => 1, 2번을 거쳐야 이게 잘 보임.
- 위와 같이 큰 문제를 작은 문제로 쪼갤 수 있으며, 작은 문제도 큰 문제와 같은 방법으로 풀 수 있고, 작은 문제들이 겹친다.
   (Overlapping SubProblem)
- 문제의 정답을 작은 문제의 정답으로부터 구할 수 있으며, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.
   (Optimal Substructure)

 

4. 코드구현

<Top-down 방식>

(1) 구현
-> '재귀호출' 방식으로 구현

 

(2)시간복잡도
= 배열에 채워 넣어야하는 값의수 x 1칸을 채우는 복잡도

<Bottom-up 방식>

(1) 구현
-> 'for문을 이용한 반복문'으로 구현

 

(2) 시간복잡도
= for 문의 반복 횟수