[백준] 1516번 게임 개발

문제: 1516번: 게임 개발

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    // 0번 인덱스 안 씀
    vector<int> costs(n + 1);
    vector<int> totalCosts(n + 1);

    vector<int> indegs(n + 1);
    vector<vector<int>> linkedList(n + 1);
    for (int i = 1; i < n + 1; i++) {
        cin >> costs[i];

        int prev;
        while (true) {
            cin >> prev;

            if (prev == -1)
                break;

            linkedList[prev].push_back(i);
            indegs[i]++; // 진입 간선 수 +1 해주기
        }
    }

    // 맨 처음 상태에서 진입 간선수가 0인 애들을 먼저 queue 에 넣어주기
    queue<int> noIndegs;
    for (int i = 1; i < n + 1; i++) {
        if (indegs[i] == 0) {
            noIndegs.push(i);
            totalCosts[i] += costs[i];
        }
    }

    // 큐가 다 비기 전까지 계속 업데이트
    while (!noIndegs.empty()) {
        int curBuilding = noIndegs.front();
        noIndegs.pop();

        for (int next : linkedList[curBuilding]) {
            indegs[next]--; // 진입 간선 수 -1 해주기

            // 지으려고 하는 건물은 이전의 지어져야 하는 모든 건물이 지어져야 지을 수 있음
            // 근데 이전에 지어야 하는 건물들의 지어지는 시간이 다름
            // 즉, 이전에 지어져야 하는 건물 중에서 가장 오래걸리는 걸 기준으로 해야함.
            // 가장 오래 걸리는게 다 지어졌다는 건 나머지 건물들도 다 지어진 거니까
            // 즉, 이미 계산되어 있는 값과 현재 지은 건물의 시간을 더한값을 비교해서 큰 값으로 값을 업데이트함,
            totalCosts[next] = max(totalCosts[next], totalCosts[curBuilding] + costs[next]);  
        
            if (indegs[next] == 0)
                noIndegs.push(next);
        }
    }

    for (int i = 1; i < n + 1; i++) {
        cout << totalCosts[i] << "\n";
    }


    return 0;
}

 

이 문제는 1005번 문제랑 거의 유사한 문제였다.

 

이번에도 문제 풀면서 오해했던 부분은 '각 건물이 완성되기까지 걸리는 최소 시간' 이었다. 나는 최소 시간이라는 것에만 몰두한 나머지 현재 값이랑 이전 값 중 더 작은 값을 채택해야 하는 줄 알았는데 아니었다;;

 

문제에서 말하는 최소 시간이라 함은.. 이전에 지어져야 하는 모든 건물들이 다 지어진 시간을 모두 고려한 '최소한 이정도의 시간은 걸린다' 인 것 같았다. 이렇게 생각하고 문제를 풀어야 풀이 방법이 떠오른다.

 

나는 건물을 짓는데 걸리는 시간은 이전 건물을 짓는데 걸리는 시간도 누적해야 하니까 당연히 수가 커질수밖에 없는데 어떻게 이를 만족하는 최소값을 구할 수 있을까?? 라고 생각하면서 머리가 안 돌아갔는데 그렇게 푸는게 아니었던 것이다..;;

 

1005번 문제 풀때도 이것때문에 시간 오래 잡아먹었는데 이번에도 똑같은 논리에서 막혀서 오래 걸렸다 -_-;;;

 

내일 다시 복습하면서 풀어봐야겠다. -_-;;;