[ACMICPC.NET] 1005번 ACM Craft

이 문제는 내가 알고리즘을 처음 풀기 위해 노력한지 어언 만 1년이 지난 이후에도 시도하였던 문제이다.

내 오답률의 일정부분 지분률을 차지하던 그당시 나에게 정말 어려웠던 문제인데..

오늘 정말 허무하게도 풀려버렸다.

내가 시도한 방법은 재귀함수를 이용한 방식의 정말 단순한 해결법이다.

1 ~ N번 까지의 건물이 존재한다고 가정하고 각 건물 사이의 빌드 관계가 주어졌을때 W 건물을 건설하기 위한 최소 시간을 출력하는 문제이다.

여기서 문제의 중요 조건이 하나 있다.

만약 1번과 2번 건물을 지어야지 3번 건물을 건설할 수 있다면 3번 건물을 건설하기 위해 걸리는 최종 시간은

max(1번 건설시간, 2번 건설시간) + 3번 건물만 건설하는 시간

위와 같은 방식이 되며, 이를 재귀 호출하는 형식으로 구현하였다.

문제의 예시처럼 1번을 건설해야 2, 3번을 건설할 수 있고, 이를 다 건설해야 4번을 건설할 수 있을때

4번의 최소 건설 시간 = max(2번의 최소 건설시간, 3번의 최소 건설시간) + 4번 건물 건설시간

이와 같은 형태가 되며, 2번과 3번의 최소 건설시간을 구하기 위해 같은 방식으로 각각을 재귀적 호출하는 방식을 선택하였을때

코드는 아래와 같다.

하지만 재귀호출에서 같은 구간이 여러번 중복적으로 호출되어질 수 있으므로 이를 메모이제이션하게 되면 풀리게 된다.

코드

#include <iostream>

#include <algorithm>

using namespace std;

int DP[1001];

int M[1001][1001], D[1001];

int solve(int W, int N) {

    if (DP[W] > 0) return DP[W];

 

    int result = 0;

    for (int i = 1; i <= N; i++) {

        if (M[W][i] == 1) {

            result = max(result, solve(i, N));

        }

    }

    return DP[W] = result + D[W];

}

int main() {

    int T;

    scanf("%d", &T);

    for (int i = 0; i < T; i++) {

        int N, K, W;

        for (int j = 0; j < 1001; j++) D[j] = DP[j] = 0;

        for (int j = 0; j < 1001; j++) for (int k = 0; k < 1001; k++) M[j][k] = 0;

 

        scanf("%d %d", &N, &K);

        for (int j = 1; j <= N; j++) scanf("%d", &D[j]);

        for (int j = 0; j < K; j++) {

            int x, y;

            scanf("%d %d", &x, &y);

            M[y][x] = 1;

        }

        scanf("%d", &W);

        printf("%d\n", solve(W, N));

    }

    return 0;

}