[백준 1005] ACM Craft 풀이노트

위 로고를 누르면 해당 문제로 이동합니다.

1차 풀이 (2018-08-07, 2380 KB, 576 MS)

 최적부분 구조에 눈치채라. 

이 문제는 건물 N의 최소건설시간을 구하는 문제이며,

건물 N을 짓기위해 필요한 건물들을 X라고 하면,

다음 포인트를 짚을 수 있어야 한다.

• 모든 X가 지어져야 N을 건설할 수 있다.

• X 내에서 최소건설시간이 가장 긴 건물이 완성되었을 때, 이미 모든 X는 건설되어 있다.

즉, solve(N)을 풀려면 선행건물들에 대한 부분문제를 풀어야 한다.

원래문제와 부분문제는 독립적이므로 최적부분 구조이다.

최적부분 구조는 동적계획법으로 해결할 수 있으며,

중복되는 부분문제를 해결하기 위해 메모이제이션(캐싱)을 활용한다.