https://www.acmicpc.net/problem/1806



투포인터를 활용해주면 된다.


길이를 언제 갱신하고, 무한루프를 어느 위치에서 종료할 것인지만 명확히 해준다면 무리없이 풀리는 문제이다.


현재까지 더한 구간합이, 넘겨야할 합보다 크다면 일단 그 시점의 길이가 최소 길이인지 비교해서 갱신해준다.


이후 왼쪽 인덱스 포인터를 증가시키고 길이를 감소시키고, 변화된 상태가 조건을 만족하는지 확인해주고 이런 흐름이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
 
using namespace std;
typedef long long ll;
const int INF = 1000000;
int main(void) {
    ll arr[100001];
    double s;
    int n;
    cin >> n >> s;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    
    int l = 0, h = 0, len = 0, Min = INF;
    ll Sum = 0;
    while (1) {
        if (Sum < s) {
            if (h > n - 1) break; //h가 n인데, 쿼리를 실행하게 하면 안된다
            Sum += arr[h];
            h++;
            len++;
        }
        else {
            if (len < Min) Min = len;
            
            Sum -= arr[l];
            l++; 
            len--;
        }
    }
    if (Min != INF)
        cout << Min << '\n';
    else
        cout << 0 << '\n';
    
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 10254 고속도로 C++  (0) 2019.08.17
백준 2458 키 순서 C++  (0) 2019.08.16
백준 11404 플로이드 C++  (0) 2019.08.16
백준 11657 타임머신 C++  (0) 2019.08.16
백준 1753 최단경로 C++  (0) 2019.08.15

https://www.acmicpc.net/problem/11404


상관없는지 모르겠으나 원래는 kij순으로 루프 돌아야한다


문제 이름에서부터 플로이드 와샬 알고리즘을 사용해야 한다는 것을 암시하고 있는 문제이다.


주의할 것은, 이전까지 INF 값으로 limits.h 헤더에 있는 INT_MAX를 사용했는데, 이 값에 어떤 값이 더해지는 연산을 하게되면 오버플로우가 발생한다.


다익스트라, 벨만포드에서는 괜찮았지만 플로이드에서 이런 일이 생기니, 그냥 속편하게 내가 INF를 지정해서 써야겠다.


INF는 항상 (간선 가중치의 최댓값 ) * (정점 개수 - 1 ) 보다 크게 잡아줘야 한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<algorithm>
#include<limits.h>
using namespace std;
int n, m;
int dis[101][101];
const int MAX = 1000000000; //INF는 항상 (간선 가중치의 최댓값) * (정점 개수 - 1) 보다 큰 값
void FW() {
    for (int k = 1; k <= n; k++) 
        for (int j = 1; j <= n; j++) 
            for(int i = 1; i <= n; i++) 
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
 
int main(void) {
    //ios::sync_with_stdio(false);
    cin.tie(0);
        
    cin >> n >> m;
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= n; j++) 
            dis[i][j] = i == j ? 0 : MAX;
        
    for (int i = 0; i < m; i++) {
        int src, dst, cost;
        cin >> src >> dst >> cost;
        dis[src][dst] = min(dis[src][dst], cost);
    }
 
    FW();
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dis[i][j] == MAX) dis[i][j] = 0;
             cout << dis[i][j] << ' ';
        }
        cout << '\n';
    }
 
    return 0;
}
 
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2458 키 순서 C++  (0) 2019.08.16
백준 1806 부분합 C++  (0) 2019.08.16
백준 11657 타임머신 C++  (0) 2019.08.16
백준 1753 최단경로 C++  (0) 2019.08.15
백준 1916 최소비용 구하기 C++  (0) 2019.08.15

https://www.acmicpc.net/problem/11657



벨만 포드 알고리즘을 사용하는 문제는 음수 가중치를 가지고 무언가를 하는 문제들인데, 거리 / 비용을 음수로 주기는 표현이 애매하기 때문에 이 문제에서처럼 시간을 가지고 문제를 만드는 것 같다. 웜홀, 시간 여행 등의 주제로 나오는 것 같다.


초기에 간선들의 정보를 받아주고, 다익스트라와 동일하게 모든 정점으로 가는 비용을 무한대로 초기화 한다.


그리고 n-1번에 거쳐서, 모든 정점들의 모든 간선들을 탐색해주고, 마지막 한 번은 음수 사이클 검사용으로 탐색해준다.


마지막 1번의 검색에서, 즉 가장 바깥 루프의 n번째 탐색시에, 경로 / 비용의 갱신이 발생한다면, 이 그래프는 음수 사이클을 포함하고 있다는 의미이다.


그렇지 않으면, 당연히 n개의 정점을 최소비용으로 이동하는 데에 n-1개의 간선이면 충분하기 때문이다.


n-1개 이상 간선을 사용한다는 것은? 어딘가에 음수 사이클이 있기 때문에 계속 그곳을 지나가게끔 갱신이 발생되고 있다는 의미이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<limits.h>
#include<utility>
#include<vector>
using namespace std;
 
typedef pair<int, int> pii;
vector<pii> v[501]; //비용, 목적지
int n, m, dis[501];
bool hasNegativeCycle = false;
void bellmanFord(int st) {
    dis[st] = 0;
    
    for (int t = 0; t < n; t++) { //n-1번 수행하고 +1번은 음수 사이클 확인용
        for (int i = 1; i <= n; i++) { //모든 정점의 간선을 확인하는 것을
            for (int j = 0; j < v[i].size(); j++) {
                int moveCost = v[i][j].first;
                int dst = v[i][j].second;
                if (dis[i] != INT_MAX && dis[dst] > dis[i] + moveCost) {
                    dis[dst] = dis[i] + moveCost;
                    if (t == n-1) hasNegativeCycle = true;
                }
            }
        }
    }
}
int main(void) {
    //ios::sync_with_stdio(false);
    cin.tie(0);
 
    //도시 n개, 엣지 m개
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int from, to, cost;
        cin >> from >> to >> cost;
        v[from].push_back({ cost, to });
    }
    
    //음수사이클 -> -1, 아니면 1번부터 각 노드까지 거리
    for (int i = 1; i <= n; i++)
        dis[i] = INT_MAX;
    bellmanFord(1);
    if (hasNegativeCycle) cout << -1 << '\n';
    else {
        for (int i = 2; i <= n; i++) {
            if (dis[i] != INT_MAX)
                cout << dis[i] << '\n';
            else
                cout << -1 << '\n';
        }
    }
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1806 부분합 C++  (0) 2019.08.16
백준 11404 플로이드 C++  (0) 2019.08.16
백준 1753 최단경로 C++  (0) 2019.08.15
백준 1916 최소비용 구하기 C++  (0) 2019.08.15
백준 11438 LCA2 C++  (0) 2019.08.15

https://www.acmicpc.net/problem/1753


다익스트라 알고리즘을 구현해주면 된다.


방문했던 노드를 다시 방문하지 않도록 해주어야 TLE를 피할 수 있을 것이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
#include<limits.h>
using namespace std;
int n, m, dist[20001];
 
typedef pair<int, int> pii;
bool vis[20001];
vector<pii> e[20001]; //비용, 목적지
priority_queue<pii, vector<pii>, greater<pii> > pq;
void dijkstra(int st) {
    dist[st] = 0;
    
    pq.push({ dist[st], st });
 
    while (!pq.empty()) {
        int here = pq.top().second;
        vis[here] = true;
        
        pq.pop();
        for (int i = 0; i < e[here].size(); i++) {
            int there = e[here][i].second;
            if (vis[there]) continue;
            int moveCost = e[here][i].first;
            if (dist[there] > dist[here] + moveCost) {
                dist[there] = dist[here] + moveCost;
                pq.push({ dist[there], there });
                
            }
        }
    }
}
int main() {
    cin >> n >> m;
    int src;
    cin >> src;
    while (m--) {
        int from, to, cost;
        cin >> from >> to >> cost;
        e[from].push_back({ cost, to });
    }
    for (int i = 1; i <= n; i++)
        dist[i] = INT_MAX;
    
 
    dijkstra(src);
    
    for (int i = 1; i <= n; i++) {
        if (dist[i] != INT_MAX) cout << dist[i] << '\n';
        else cout << "INF" << '\n';
    }
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 11404 플로이드 C++  (0) 2019.08.16
백준 11657 타임머신 C++  (0) 2019.08.16
백준 1916 최소비용 구하기 C++  (0) 2019.08.15
백준 11438 LCA2 C++  (0) 2019.08.15
백준 1197 최소 스패닝 트리 C++  (0) 2019.08.15

https://www.acmicpc.net/problem/1916


가중치가 있는 그래프의 최소 비용 / 최단 경로를 구하는 문제이다.


가중치들이 모두 양수이기 때문에 다익스트라를 이용한다.



먼저 시작점으로부터 i번 노드까지 가는 총 비용을 의미하는 dist[i]를 무한대로 초기화한다.



알고리즘이 시작되면, 시작점으로부터 시작점까지의 비용은 0인 것이 자명하기 때문에 dist[시작점] = 0으로 바꿔준다.


그리고 시작점으로부터의 거리가 가장 낮은 것부터 뽑을 것이기 때문에 min heap을 사용한다.



이 때, pair에 특정 노드번호와, 그 노드까지 가는 비용을 함께 관리할 것이다. 주의할 점은, pair의 대소 비교는 first부터 일어나기 때문에 반드시 비용을 first에 넣어줄 수 있도록 한다.



이후로는 현재노드까지 오는 비용 + 이동할 수 있는 노드로의 이동 비용 < 다음 노드까지 가는 총비용


위의 경우에 다음 노드까지 가는 총 비용을 갱신해준다.


갱신되는 경우에, heap에 갱신되는 지점을 넣어주도록 하자.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
#include<limits.h>
using namespace std;
int n, m, dist[20001];
 
typedef pair<int, int> pii;
bool vis[20001];
vector<pii> e[20001]; //비용, 목적지
priority_queue<pii, vector<pii>, greater<pii> > pq;
void dijkstra(int st) {
    dist[st] = 0;
    
    pq.push({ dist[st], st });
 
    while (!pq.empty()) {
        int here = pq.top().second;
        vis[here] = true;
        
        pq.pop();
        for (int i = 0; i < e[here].size(); i++) {
            int there = e[here][i].second;
            if (vis[there]) continue;
            int moveCost = e[here][i].first;
            if (dist[there] > dist[here] + moveCost) {
                dist[there] = dist[here] + moveCost;
                pq.push({ dist[there], there });
                
            }
        }
    }
}
int main() {
    cin >> n >> m;
 
    while (m--) {
        int from, to, cost;
        cin >> from >> to >> cost;
        e[from].push_back({ cost, to });
    }
    for (int i = 1; i <= n; i++)
        dist[i] = INT_MAX;
    
    int src, dst;
    cin >> src >> dst;
    dijkstra(src);
    
    cout << dist[dst];
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 11657 타임머신 C++  (0) 2019.08.16
백준 1753 최단경로 C++  (0) 2019.08.15
백준 11438 LCA2 C++  (0) 2019.08.15
백준 1197 최소 스패닝 트리 C++  (0) 2019.08.15
백준 1516 게임 개발 C++  (0) 2019.08.15

https://www.acmicpc.net/problem/11438


최소 공통 조상 (Lowest Common Ancestor)를 찾는 알고리즘이다.


1. dfs로 트리를 만든다. 이때 노드별 깊이 정보와(root 깊이 = 0) 가장 첫번째 부모 정보를 잡아준다.


2. 노드 A의 2^k번째 부모 노드는, A의 2^k-1번째 부모 노드의 2^k-1번째 부모 노드와 같다는 것을 이용해서 바텀업 dp로 부모 배열을 채운다.


3. 공통 조상을 찾을 a, b가 있다면, 우선 깊이가 깊은 곳과 낮은 곳을 확실히 구분해준다. 그리고 둘의 높이를 맞춰준다.


n개의 노드가 있다고 했을 때, 2의 거듭제곱으로 타고 올라갈 수 있는 최대 높이가 MAXK =(int)floor(log2(n)); 이다.


두 노드의 높이 차이가, 위에서부터 보고 내려온 2의k승보다 크거나 같아지는 순간마다 깊은 노드를 해당하는 2의 k번째 부모로 갱신한다.


결국 높이가 같아지게 되고, 이때 두 노드의 값이 같다면 반환해주면 된다.



그렇지 않다면


4. 위와 비슷한 방식으로, 2의최대 거듭제곱부터 아래로 내려오면서 부모의 노드가 같은지 확인한다. 다를때마다 두 노드를 다른 순간의 2의 k승번째 노드로 갱신해준다. 결국 둘이 같아지게 된다


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
 
int n, m, dep[100002], MAXK, parent[100002][20];
bool  vis[100002];
 
vector<int> e[100002];
void makeTree(int here, int depth) { //트리 만들면서 첫번째 부모와 깊이를 채움
    //if (vis[here]) return; //continue문 주석 풀고 여길 주석해도 똑같음
    vis[here] = true;
    dep[here] = depth;
    
    for (int i = 0; i < e[here].size(); i++) {
        int next = e[here][i];
        if (vis[next]) continue;
        parent[next][0] = here; //첫번째 부모 저장
        makeTree(next, depth + 1);
    }
}
void fillParent() { //바텀업으로 부모 배열 채워줌
    for (int k = 1; k <= MAXK; k++) 
        for (int i = 1; i <= n; i++) 
            parent[i][k] = parent[parent[i][k - 1]][k - 1];
}
int lca(int swall, int deep) {
    if (dep[deep] < dep[swall]) swap(deep, swall);
    
    for (int k = MAXK; k >= 0; k--) { //높이를 동일하게 맞춰줌
        int dif = dep[deep] - dep[swall];
        if (dif >= (1 << k)) deep = parent[deep][k];
    }
 
    if (deep == swall)
        return deep;
    
    //printf("deep  swall 중간 %d %d\n", deep, swall);
    for (int k = MAXK; k >= 0; k--) {
        if (parent[deep][k] != parent[swall][k]) {
            deep = parent[deep][k];
            swall = parent[swall][k];
        }
    }
    return parent[deep][0];
 
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    for (int i = 0; i < n-1; i++) { //node가 n개고 간선은 n-1개
        int src, dst;
        cin >> src >> dst;
        e[src].push_back(dst);
        e[dst].push_back(src);
    }
    makeTree(1, 0); //root = 1, root depth = 0
    
    MAXK =(int)floor(log2(n)); //포함 -> 최대높이*****************
    
    fillParent();
 
    cin >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << '\n';
    }
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1753 최단경로 C++  (0) 2019.08.15
백준 1916 최소비용 구하기 C++  (0) 2019.08.15
백준 1197 최소 스패닝 트리 C++  (0) 2019.08.15
백준 1516 게임 개발 C++  (0) 2019.08.15
백준 2056 작업 C++  (0) 2019.08.15

https://www.acmicpc.net/problem/1197


MST를 구현해주면 되고, 크루스칼 알고리즘을 이용한다.


크루스칼 알고리즘은 유니온 파인드를 그대로 옮겨 놨다고 봐도 상관이 없다.


0. 유니온 파인드를 활용하기 때문에, 최상위 부모노드의 값을 자기 자신으로 초기화한다.


1. 간선 정보를 비용 오름차순으로 정렬한다.


2. 간선의 시작점과 끝점을 union해보면서, 같은 그룹에 속해있지 않다면, union 해주고 간선 비용을 추가해준다.

이미 같은 그룹이라면 연결되어 있다는 의미이기 때문에 비용에 더해주지 않고 스킵한다.


3. 모든 노드를 연결하는데에 필요한 간선의 개수는 n-1개이다. 따라서 n-1개 만들었으면 그만두고 반복문을 빠져나오자.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
 
int n, e, r[10002];
struct EDGE {
    int from, to, cost;
};
vector<EDGE> edge;
bool cmp(EDGE a, EDGE b) {
    return a.cost < b.cost;
}
int getParent(int a) {
    if (r[a] == a) return a;
    else return r[a] = getParent(r[a]);
}
bool join(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if (a == b) return false; //이미 연결되어 있음
    else if (a < b)
        r[b] = a;
    else
        r[a] = b;
    return true;
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> e;
 
    while (e--) {
        int src, dst, cost;
        cin >> src >> dst >> cost;
        edge.push_back({ src, dst, cost });
    }
    sort(edge.begin(), edge.end(), cmp);
 
    for (int i = 1; i <= n; i++)
        r[i] = i;
 
    //연결 안 되어 있는 노드 찾아서 연결 해보고, 연결 안 되어 있으면 연결하고 비용 추가
    ll res = 0;
    int cnt = 0;
    for (int i = 0; i < edge.size(); i++) {
        if (join(edge[i].from, edge[i].to)) {
            res += edge[i].cost;
            cnt++;
            if (cnt == n - 1) break;
        }
    }
    printf("%lld ", res);
 
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1916 최소비용 구하기 C++  (0) 2019.08.15
백준 11438 LCA2 C++  (0) 2019.08.15
백준 1516 게임 개발 C++  (0) 2019.08.15
백준 2056 작업 C++  (0) 2019.08.15
백준 1766 문제집 C++  (0) 2019.08.15

https://www.acmicpc.net/problem/1516



각 단계별로 시간(비용)이 있을 때, 위상 정렬을 할 수 있는 정보가 주어지는 경우이다.


입력을 받을 때, indegree를 모두 구하면서 입력을 받는다.


초기에 indegree가 0인 지점을 큐에 넣고 시작하는데, 이런 지점은 이전에 필요로 하는 단계가 없기 때문에, 그 지점의 비용이


그 지점까지 총 비용이 된다.



이후에는 위상 정렬을 진행하는데, 현재 단계까지의 총 비용은 확정이므로, 다음 단계의 총 비용을 구해준다. 이 때, 시간의 경우, 가장 오래걸리는 시간을 넣어줘야 한다.


이게 당연한 것이, 4번을 수행하기 위해 1번과 3번을 사전에 수행해야 한다고 해보자.


다른 조건이 없다는 가정하에, 1번과 3번중에서는 어떤 것을 먼저해도 상관이 없다.


그렇다면 예를들어 1번을 하는데에 3초가 걸리고, 3번을 하는데에 6초가 걸린다고 쳐보자. 그리고 4번만을 수행하는 데에는 5초가 걸린다고 하자.


1번을 볼 때, 1번 다음에 4번을 수행해야 한다는 것을 알고 있고, 이 시점에서 4번을 완수하기 위해서는 1번의 시간 + 4번의 시간이 필요하다.


1번을 하면서 동시에 3번도 수행할 수 있기 때문에, 앞서 구한 1번 시간 + 4번시간과 3번 시간 + 4번시간을 비교해서, 오래 걸리는 시간으로 갱신해줘야 한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
int t[502], n, ind[502], done[502];
vector<int> v[502];
queue<int> q;
 
void tpgSort() {
    for (int i = 1; i <= n; i++)
        if (ind[i] == 0) {
            q.push(i);
            done[i] = t[i];
        }
 
    for (int i = 0; i < n; i++) {
        if (q.empty()) cout << "cycle\n";
 
        int cur = q.front();
        q.pop();
        
            int Max = -1;
            for (int j = 0; j < v[cur].size(); j++) {
                ind[v[cur][j]]--;
                if (ind[v[cur][j]] == 0) q.push(v[cur][j]);
                //다음 단계 비용 = 현재 단계까지 총비용중 가장 오래걸리는 비용 + 다음 단계 비용
                if (done[v[cur][j]] < done[cur] + t[v[cur][j]]) {
                    done[v[cur][j]] = done[cur] + t[v[cur][j]];
                }
            }
 
    }
}
int main(void) {
    
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int time;
        cin >> time;
        t[i] = time;
        while (1) {
            int pre;
            cin >> pre;
            if (pre == -1) break;
            v[pre].push_back(i);
            ind[i]++;
        }
    }
    tpgSort();
    for(int i = 1 ; i <= n ; i++ )
        printf("%d\n", done[i]);
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 11438 LCA2 C++  (0) 2019.08.15
백준 1197 최소 스패닝 트리 C++  (0) 2019.08.15
백준 2056 작업 C++  (0) 2019.08.15
백준 1766 문제집 C++  (0) 2019.08.15
백준 2252 줄 세우기 C++  (0) 2019.08.15

https://www.acmicpc.net/problem/2056


dp느낌으로 해결이 가능하다. . 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다


이 문장때문에 아래 풀이로 가능한 것이다.


d[i] = i의 사전작업까지 모두 포함해서 작업 i를 끝내는 데에 걸리는 시간


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
#include<iostream>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
 
int n, m, t[10001], d[10001];
vector<int> v[10001];
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int tm, num;
        cin >> tm >> num;
        t[i] = tm;
        while (num--) {
            int pre;
            cin >> pre;
            v[i].push_back(pre);
        }
    }
    //d[i] = i의 사전작업까지 다 포함해서 작업 i 끝내는데 드는 시간
    d[1] = t[1];
    for (int i = 2; i <= n; i++) {
        if (v[i].size() == 0) d[i] = t[i]; //사전 작업 없으면 그 작업 끝내는 시간
        else {
            int Max = -1;
            for (int j = 0; j < v[i].size(); j++) {
                if (Max < d[v[i][j]]) Max = d[v[i][j]];
            }
            d[i] = Max + t[i];
        }
    }
    //어떤 작업이 제일 마지막에 끝날지는 알 수 없지만, 필요 시간이 가장 긴게 마지막에 끝나는 것
    int ret = -1;
    for (int i = 1; i <= n; i++)
        if (ret < d[i]) ret = d[i];
    cout << ret;
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1197 최소 스패닝 트리 C++  (0) 2019.08.15
백준 1516 게임 개발 C++  (0) 2019.08.15
백준 1766 문제집 C++  (0) 2019.08.15
백준 2252 줄 세우기 C++  (0) 2019.08.15
백준 4195 친구 네트워크 C++  (0) 2019.08.14

https://www.acmicpc.net/problem/1766


풀어야할 문제들이 난이도로 주어진다. 또한 어떤 문제를 어떤 문제보다 먼저 풀어야한다는 식의 데이터가 주어지므로, 위상 정렬을 활용한다.


다만 큐에서 꺼낼때, 난이도가 낮은 문제를 먼저 꺼내야 하기 때문에, min heap을 사용해주면 된다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
#include<iostream>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
 
int n, m, ind[32002];
vector<int> v[32002];
priority_queue<int, vector<int>, greater<int> > q;
void tpgSort() {
    for (int i = 1; i <= n; i++) { //indegree 0인거 큐에 넣고 시작
        if (ind[i] == 0) q.push(i);
    }
 
    for (int i = 0; i < n; i++) { // 노드의 개수보다 더 많이 돌면 사이클
        if (q.empty()) cout << "cycle occured\n";
 
        int cur = q.top(); q.pop();
        cout << cur << ' '; //노드 삭제
 
        
        for (int i = 0; i < v[cur].size(); i++) {
            ind[v[cur][i]]--; //삭제된 노드와 연결된 간선 제거
            if (ind[v[cur][i]] == 0) q.push(v[cur][i]);
        }
 
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
 
    while (m--) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        ind[b]++;
    }
    tpgSort();
 
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1516 게임 개발 C++  (0) 2019.08.15
백준 2056 작업 C++  (0) 2019.08.15
백준 2252 줄 세우기 C++  (0) 2019.08.15
백준 4195 친구 네트워크 C++  (0) 2019.08.14
백준 1717 집합의 표현 C++  (0) 2019.08.14

+ Recent posts

티스토리툴바