BOJ 1005. ACM Craft

 

문제 링크 

 

문제 풀이

 누가 봐도 위상정렬을 사용하는 문제이지만 처음 보자마자 그냥 dp로 풀 수 있을 것 같아서 dp로 시도해보았다. 일단 유향그래프니까 각 점에서 들어오는 선분에 연결된 점들을 graph에 저장해주었다. 또 time이라는 배열에 각 건물을 짓는데 걸리는 시간을 저장하였다.

 dp를 아래와 같이 정의하자.

$dp[i] :=$ 건물 $i$를 건설완료 하는데 드는 최소 시간

 그러면 아래와 같은 점화식을 얻을 수 있다.

이전 건물들을 지을 때까지 걸리는 시간중 최대 시간

 

 시간복잡도는 $O(NK)$이므로 dp로 해도 시간초과는 나지 않을 것이다.

 

시행 착오

문제에서 여러개의 테스트 케이스가 주어지는데 각 테스트 케이스마다 graph를 초기화하지 않았다. 근데 신기하게도 예제 1번은 통과해서 조금 고민했었다. 그리고 graph를 초기화해야한다는 사실을 알고 나서도 전역 변수로 지정된 벡터 배열을 어떻게 초기화해야하는지 몰라서 ChatGPT에게 물어봤다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int t[1001],dp[1001],N,W;
vector<int> graph[1001];

int solve(int x)
{
    int& rv = dp[x];
    if(rv!=-1)return rv;
    
    rv = t[x];
    int mx=0;
    for(int i=0;i<graph[x].size();i++)
    {
        mx = max(mx,solve(graph[x][i]));
    }
    rv += mx;
    return rv;
}
void input()
{
    int K;
    cin>>N>>K;
    for(int i=1;i<=N;i++)
    {
        cin>>t[i];
    }
    while(K--)
    {
        int u,v;
        cin>>u>>v;
        graph[v].push_back(u);
    }
    cin>>W;
    
    for(int i=1;i<=N;i++)
    {
        dp[i] = -1;
    }
}
int main()
{   
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--)
    {
        input();
        int ans = solve(W);
        cout<<ans<<"\n";
        for(int i = 1; i <= N; i++)
        {
            graph[i].clear();
        }
    }
}