[수업]재활용 수집통(Recycling Bins)

Intro..

이 문제는 DP 관련 문제이다.

DP 관련해서 정리해둔 게시글이 있기 때문에 참고할 것.

문제

풀이

이 문제는 top-down 방식으로 문제를 해결했었다.

m=1때 규칙은 손으로 그려보면 금방 구할 수 있어서 간단히 구하였고, m>=2 이상이 문제이다.

• m은 쓰레기통 수이다.

• m>=2 이상은 min을 구해야 함.

  • n m이 6 2 의경우? 6개 집, 2개쓰레기통 이니까 쓰레기통 2,3,4,5,6개때 경우 전부 비교
  • 왜냐면 이때 통위치 다 달라지니까 그때 비교중 제일 min값 사용

또한 아래는 bottom-top 방식으로 교수님이 푸신 풀이가 있으니 이 방식을 참고해도 좋다.