[알고리즘 공부/G1/Python3, C++]

17942번 알고리즘 공부 G1

 

문제
늘 돈이 부족한 희정이는 HCPC에 참가하여 좋은 성적을 거두어서 상금을 타기로 마음먹었다. 이를 위해 먼저 출제위원장인 정호의 노트북을 해킹하여 N개의 알고리즘을 출제 범위로 두고 문제가 출제된다는 사실을 알게 되었다. 출제 범위를 알았으니 이제 희정이에게 남은 것은 알고리즘을 공부하는 것이다. 알고리즘 공부에는 사실 특별한 규칙이 숨어있는데 이는 다음과 같다. 각 알고리즘들을 처음 배울 때에는 Ki만큼의 알고리즘 공부량이 필요하다. 그리고 몇몇 알고리즘은 서로 연관성이 있어 어느 한 알고리즘을 배우면 다른 특정한 알고리즘을 배울 때 필요한 공부량이 줄어드는 경우가 있다. 한 알고리즘을 배울 때 필요한 공부량이 여러 개의 다른 알고리즘에 의해서 줄어드는 경우는 그 감소량을 모두 합산해서 적용한다. 또한 알고리즘 공부량은 소모되지 않으며 누적된다. 예시로 처음 배울 때 3의 공부량이 필요한 알고리즘과 5의 공부량이 필요한 알고리즘을 모두 배우기 위해선 그 둘의 합 8이 아니라 그 둘의 최댓값 5의 공부량이 필요하다. 그러나 막상 알고리즘 공부를 하려고 보니 벌써부터 중간고사가 닥쳐오고 있었기 때문에 모든 알고리즘을 배우기에는 시간이 부족했다. 희정이는 결국 최소한의 시간을 투자해 최소한 M개의 알고리즘만이라도 공부하기로 결심했다. 당신이 할 일은 알고리즘을 처음 배우는데 필요한 공부량과 각 알고리즘 사이의 연관성이 주어졌을 때, 최소 M개의 알고리즘 배우는데 필요한 알고리즘 공부량을 구하는 것이다.

입력
첫째 줄에는 출제 범위인 알고리즘의 개수를 나타내는 양의 정수 N, 최소한 배우고자 하는 알고리즘의 개수를 나타내는 양의 정수 M이 주어진다. ( 1 ≤ M ≤ N ≤ 100,000 )둘째줄에는 각 알고리즘을 처음 배우는데 필요한 알고리즘 공부량을 나타내는 N개의 양의 정수 Ki가 사이에 공백을 두고 주어진다. (1 ≤ Ki ≤ 10^8) 셋째 줄에는 서로 연관성이 있는 알고리즘 관계의 개수를 나타내는 양의 정수 R이 주어진다. ( 0 ≤ R ≤ 100,000 ) 다음 K줄에 걸쳐서, 각 줄에 A, B, D가 주어지며 이는 A번 알고리즘을 배우면 B번 알고리즘을 배우는데 필요한 공부량이 D만큼 줄어듦을 의미한다. (1 ≤ A, B ≤ N, 1 ≤ D ≤ 108) A와 B의 쌍이 같은 관계가 여러 번 주어지지 않으며, A = B인 관계는 주어지지 않는다. 또한, 공부량이 아무리 줄어도 0 이하로 내려가지 않음이 보장된다.

출력
최소 M개의 알고리즘을 익히기 위해서 필요한 최소 알고리즘 공부량을 출력하여라.

 

 

자료 구조, 그래프 이론, 그리디 알고리즘, 그래프 탐색, 우선순위 큐

 

알고리즘의 공부량은 소모되지 않고 누적되기 때문에, 최종적으로 M개의 알고리즘 중 필요한 공부량의 최댓값이 정답이 된다.

 

현재 공부할 수 있는 알고리즘 중 공부량이 가장 작은 알고리즘부터 학습을 하는 탐욕알고리즘을 택했다.

가장 작은 공부량을 구하기 위해 우선순위 큐 자료구조를 택했다. 

 

최소힙에서 꺼낸 알고리즘을 공부하면 감소되는 알고리즘들의 공부량을 처리하고, 해당 값을 최소힙에 넣었다.

이때 이미 배운 알고리즘은 제외하는 방식을 통해 너무 많은 값이 최소힙에 들어가지 않도록 했다.

 

 

import sys
import heapq
n, m = map(int, sys.stdin.readline().split())
subs = [0] + list(map(int, sys.stdin.readline().split()))

routes = [[] for _ in range(n+1)]
done = [False] * (n+1)

for _ in range(int(sys.stdin.readline())):
    s, e, c = map(int, sys.stdin.readline().split())
    routes[s].append((e, c))

hq = []
for i in range(1, n+1):
    heapq.heappush(hq, (subs[i], i))

cnt, cur_max = 0, 0
while cnt < m:
    v, i = heapq.heappop(hq)
    if done[i]: continue
    cnt += 1
    cur_max = max(cur_max, v)
    done[i] = True
    for vv, c in routes[i]:
        if done[vv]: continue
        subs[vv] -= c
        heapq.heappush(hq, (subs[vv], vv))
        
print(cur_max)

 

 

 

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

using namespace std;

int subs[100001];
bool done[100001];
vector<pair<int, int>> routes[100001];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minpq;

    int n, m; cin>>n>>m;
    for (int i = 1; i<=n; ++i)
    {
        int v; cin>>v;
        subs[i] = v; done[i] = false;
        minpq.push(make_pair(v, i));
    }

    int r; cin>>r;
    while (r--)
    {
        int s, e, c; cin>>s>>e>>c;
        routes[s].push_back(make_pair(e, c));
    }

    int max_v = 0;
    while(m)
    {
        int v = minpq.top().first, i = minpq.top().second;
        minpq.pop();
        if (done[i]) continue;
        done[i] = true; --m; 
        max_v = max(v, max_v);
        for (auto data : routes[i])
        {
            if (done[data.first]) continue;
            subs[data.first] -= data.second;
            minpq.push(make_pair(subs[data.first], data.first));
        }
    }
    cout<<max_v;
}

 

---

 

그리디 알고리즘에 맞게 아이디어만 찾아낸다면 구현은 편한 문제에 속한다.

난이도 기여를 하지는 않았으나, G2~G3정도를 줄 것 같다.