동적 계획법(DP) + 메모이제이션(Memoization)

동적 계획법 + 메모이제이션

백준 1005번 : ACM Craft

문제를 처음 보자마자 DFS가 가장 먼저 생각났다.

2중 벡터를 만들어 각각의 인덱스에 하위 건물들의 번호를 푸쉬하고
최종적으로 목표건물부터 시작해서 완전탐색을 진행하여
가장 멀리 있는 건물까지 걸리는 시간을 구했다.

결과는 꽝이었다.
주어진 테스트케이스에 대해서는 문제가 없었지만
제출하자마자 바로 시간초과가 났다.

코드를 최대한 중복없이 최적화시켜봤지만 똑같았다.
근본적으로 DFS완전탐색을 선택한 것 자체가 문제임을 깨달았다.

그래서 그다음으로 생각하게 된 것이 DP였다.
지금생각하면 당연히 DP가 훨씬 유리한데 왜 DFS부터 생각했는지 모르겠다.

DP는 큰 문제를 작은 문제로 분할하여 계산하는 방식이라고들 한다.
요컨대, 바로 해결하기 힘든 문제를 해결하기 쉬운 작은 문제들로 나누고,
가장 작은문제부터 힌트삼아 다시 쌓아올라가는 방식이라고 할 수 있을 것 같다.

그런데 만약 내가 구하고자 하는 문제가 많은 하위 문제를 갖고,
그 하위 문제들이 각각 중복되는 또 많은 하위문제들을 갖는다면
같은 하위문제를 여러번 반복해서 해결해야 하는 낭비가 생긴다.

이러한 과정에서 메모이제이션 기법이 함께 많이 사용된다.

말 그대로 작은 문제들에 대하여 그 최적해를 각각 저장(메모)해놓는 것이다.
그 뒤에 다시금 이 작은 문제의 최적해를 필요로 한다면,
다시 계산하지 않고 기존에 메모해놓았던 정보만 가져가도록 하는것이다.

문제에서의 활용

DFS로 구현할 때와 똑같이 하위 건물들의 정보가 들어있는 2중벡터 forBuild를 구성했다.
cost배열은 각 건물들이 지어지는데 걸리는 시간이 저장되어있다.

그리고 메모이제이션을 위한 d배열을 만들었고,
이 배열에는 인덱스에 해당하는 번호의 건물이 지어지기까지 걸리는 시간을 메모했다.

최종 목적 건물의 인덱스로 dp함수를 호출하였으며,

int dp(int now)
{
    if (d[now] != -1)
        return d[now];

    if (forBuild[now].empty())
        d[now] = cost[now];
    else
        for (auto& e : forBuild[now])
            d[now] = (d[now] > dp(e) + cost[now]) ? d[now] : (dp(e) + cost[now]);

    return d[now];
}

dp함수 내에서는

1. 만약 이미 메모가 되어있다면, 메모를 리턴.
2. 해당 건물의 하위 건물이 없다면, 건물의 cost만 리턴.
3. 해당 건물의 하위 건물이 있다면,
   그 건물들의 인덱스로 다시금 dp함수를 호출하여 얻어낸 값중 가장 큰 값에
   지금 건물의 cost를 더하여 리턴.

와 같은 순서로 진행된다.

3번에서 가장 큰 값을 구하는 이유는
문제에서 건물을 짓기 위해선 하위 건물들이 모두 지어져야 한다고 했기 때문이다.
즉, 가장 큰 값이라 함은 하위 건물중 가장 늦게 지어지는 건물을 뜻한다.

테스트케이스 해설

문제에서 주어진 예시를 위의 과정으로 풀어내보면

1. dp(4) 호출. 이 때, d[4]는 메모되어 있지 않고, forBuild[4]는 2, 3을 갖는다.
2. dp(4)가 dp(2) 호출. 이 때, d[2]는 메모되어 있지 않고, forBuild[2]는 1을 갖는다.
3. dp(2)가 dp(1) 호출. 이 때, d[1]은 메모되어 있지 않고, forBuild[1]은 비어있으므로
   1번건물의 cost인 10이 d[1]에 메모되고 이를 반환한다.

   d[1]	d[2]	d[3]	d[4]
   10	-1	-1	-1

4. 반환된 d[1]에 2번건물의 cost인 1을 더해 d[2]에 메모된다.
   모든 원소를 탐색했으므로 d[2]를 반환한다.

   d[1]	d[2]	d[3]	d[4]
   10	11	-1	-1

5. 반환된 d[2]에 4번건물의 cost인 10을 더해 d[4]에 메모된다.

   d[1]	d[2]	d[3]	d[4]
   10	11	-1	21

6. dp(4)가 dp(3) 호출. 이 때, d[3]은 메모되어 있지 않고, forBuild[3]은 1을 갖는다.
7. dp(3)이 dp(1) 호출. d[1]은 이미 메모되어있으므로 d[1]을 반환한다.
8. 반환된 d[1]에 3번건물의 cost인 100을 더해 d[3]에 메모된다.
   모든 원소를 탐색했으므로 d[3]을 반환한다.

   d[1]	d[2]	d[3]	d[4]
   10	11	110	21

9. 반환된 d[3]에 4번건물의 cost인 10을 더해, 메모된 d[4]와 비교한다.
   d[3]에 10을 더한 값이 기존의 d[4]보다 크므로, d[4]에 d[3] + 10을 메모한다. 모든 원소를 탐색했으므로 d[4]를 반환한다.

   d[1]	d[2]	d[3]	d[4]
   10	11	110	120

이러한 과정을 통하여 d[4]는 10 + 100 + 10 = 120 이라는 값을 갖게 된다.