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

+ Recent posts

티스토리툴바