알고리즘18 다이나믹 프로그래밍 마지막

728x90

금화모으기

둘 중에 큰 값을 골라서 (i,j)의 코인을 더한다.

8원을 거슬려주는 방법 중 1원 동전을 한개 쓰는 방법은

8-1=7원을 거슬러주는 방법

연속으로 일할 수 없다.

critical idea : 끝나는 순서를 보면된다.

3: 15만원이 최대

4: 20이 최대

5: 30이 최대

6: 30 (T9를 가져가게되면 T5를 가져가게 되고 27만원보다 전날까지 일한 것이 더 비쌈)

7. 15+25=40

8. 8번째 끝나는 일이없음

9. (20+27)=47 (T3을 가져오면 42)

10. 49

선택하지않으면 전날까지 받은 돈과 같음

p(j) = 마지막 작업과 안겹치는 작업 중 마지막 작업 (☆)

끝나는 날짜로 sorting이 되어있기 때문에 시작날짜를 넣어 binary search

n개 중 k개 고르기

모든 집합을 두 집합으로 나눈다,

-> 1을 포함 -> n-1개에서 k-1개 고르기

- >1을 미포함 -> n-1개에서 k개 고르기

n개중에 k개고르기

계산을 통해서도 알 수 있지만 2가지 경우로 나누어 알 수 있다는 것!

(겹치지않는 식에 대해서 더하기하는 것임)