2024-03-06

-작업(2056, 백준)

 ACM craft라는 문제와 똑같다. 순서가 정해져있기에 위상정렬을 떠올릴 수 있다. 기초적인 위상 정렬 문제이다. 위상 정렬에서 진입차수를 제거해갈 때, 해당 노드의 값을 갱신 시켜준다. (선행 노드가 걸리는 시간중 가장 최대 시간이 지난 후, 작업이 가능하다는 점을 생각해보자)

<소스 코드>

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int time[10010], ans[10010], ent[10010];
vector <int> vec[10010];
int n;

int main()
{
	int i, j;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		time[i] = x;
		for (j = 0; j < y; j++) {
			int t;
			scanf("%d", &t);
			vec[i].push_back(t);
			ent[t]++;
		}
	}
	queue <int> q;
	for (i = 1; i <= n; i++) {
		if (ent[i] == 0) {
			q.push(i);
			ans[i] = time[i];
		}
	}
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (i = 0; i < vec[now].size(); i++) {
			int nw = vec[now][i];
			ent[nw]--;
			if (ent[nw] == 0) {
				q.push(nw);
			}
			ans[nw] = max(ans[nw], ans[now] + time[nw]);
		}
	}
	int res = -2e9;
	for (i = 1; i <= n; i++) res = max(res, ans[i]);
	printf("%d", res);
	return 0;
}

-음악프로그램(2623, 백준)

 순서를 결정해야 되는 문제이다. 우선순위를 갖는 여러 그래프를 갖고 새로운 우선순위를 만들면된다. 새로운 우선순위에서 사이클이 발생한다면, 0을 출력하고, 아니라면 queue에서 나온 순서를 역순으로 출력해주면되는 간단한 문제이다.

<소스 코드>

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

int n, m;
vector <int> vec[1010];
vector <int> rk[1010];
int ent[1010], ch[1010];
vector <int> ans;
queue <int> q;

int main()
{
    int i, j;
    scanf("%d %d", &n, &m);
    for(i=0;i<m;i++) {
        int x;
        scanf("%d", &x);
        for(j=0;j<x;j++) {
            int y;
            scanf("%d", &y);
            rk[i].push_back(y);
        }
    }
    for(i=0;i<m;i++) {
        for(j=0;j<rk[i].size();j++) {
            for(int l = 0;l<j;l++) {
                vec[rk[i][j]].push_back(rk[i][l]);
                ent[rk[i][l]]++;
            }
        }
    }
    for(i=1;i<=n;i++) if(ent[i] == 0) q.push(i);
    while(!q.empty()) {
        int now = q.front();
        ch[now] = 1;
        ans.push_back(now);
        q.pop();
        for(i=0;i<vec[now].size();i++) {
            int nw = vec[now][i];
            ent[nw]--;
            if(ent[nw] == 0) q.push(nw);
        }
    }
    for(i=1;i<=n;i++) {
        if(ch[i] == 0) {
            printf("0");
            return 0;
        }
    }
    for(i=ans.size()-1;i>=0;i--) printf("%d\n", ans[i]);
    return 0;
}

-최소비용 구하기 2(11779, 백준)

 간단한 최소경로 탐색 문제이다. n과 m범위가 크기에 Dijkstra를 돌려 풀어줬다.

<소스 코드>

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int n, m;
vector<pair<int, int>> vec[1010];
int dis[1010];
int s, e;
int way[1010];
vector <int> ans;

void Dijkstra(int x)
{
    int i, j;
    priority_queue <pair<int, int>> pq;
    dis[x] = 0;
    pq.push({0, x});
    while(!pq.empty()) {
        int now_idx = pq.top().second, now_val = -pq.top().first;
        pq.pop();
        if(dis[now_idx] < now_val) continue;
        for(i=0;i<vec[now_idx].size();i++) {
            int idx = vec[now_idx][i].first, val = now_val + vec[now_idx][i].second;
            if(dis[idx] > val) {
                dis[idx] = val;
                pq.push({-val, idx});
                way[idx] = now_idx;
            }
        }
    }
}

void DFS(int x)
{
    if(x == -1) return;
    else {
        ans.push_back(x);
        DFS(way[x]);
    }
}

int main()
{
    int i, j;
    scanf("%d %d", &n, &m);
    for(i=0;i<m;i++) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        vec[x].push_back({y, z});
    }
    scanf("%d %d", &s, &e);
    for(i=1;i<=n;i++) dis[i] = 2e9;
    Dijkstra(s);
    printf("%d\n", dis[e]);
    way[s] = -1;
    DFS(e);
    printf("%d\n", ans.size());
    for(i=ans.size() - 1;i>=0;i--) printf("%d ", ans[i]);
    return 0;
}

-파티(1238, 백준)

 다익 응용 문제이다.각 마을에서 목적지 k 노드까지의 최단거리와, k노드에서 모든 노드까지의 최단거리를 이용하여 구하면 된다. 다익을 여러번 돌려야 하기에 dis배열 초기화에 주의하자.

<소스 코드>

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

int n, m, k;
int dis[1010];
vector <pair<int, int>> vec[1010];

int Dijkstra(int s, int e)
{
    int i, j;
    int dis[1010];
    priority_queue <pair<int, int>> pq;
    pq.push({0, s});
    for(i=1;i<=n;i++) dis[i] = 2e9;
    dis[s] = 0;
    while(!pq.empty()) {
        int now_val = -pq.top().first, now_idx = pq.top().second;
        pq.pop();
        if(dis[now_idx] < now_val) continue;
        for(i=0;i<vec[now_idx].size();i++) {
            int idx = vec[now_idx][i].first, val = now_val + vec[now_idx][i].second;
            if(dis[idx] > val) {
                dis[idx] = val;
                pq.push({-val, idx});
            }
        }
    }
    return dis[e];
}

int main()
{
    int i, j;
    scanf("%d %d %d", &n, &m, &k);
    for(i=0;i<m;i++) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        vec[x].push_back({y, z});
    }
    for(i=0;i<=n;i++) dis[i] = 2e9;
    int res = -2e9;
    for(i=1;i<=n;i++) {
        int x = Dijkstra(i, k) + Dijkstra(k, i);
        if(x > res) res = x;
    }
    printf("%d", res);
    return 0;
}

-책 정리(1818, 백준)

 줄 세우기라는 문제와 같은 문제였다. 문제에서 주어진 조건은 결국 몇명을 움직여 오름차순을 만드느냐 이기때문에 움직이지 않아도 되는 사람의 수를 구해 전체 사람수에서 빼주면된다. 이때 움직이지 않아도 되는 사람 수가 LIS이다.

<소스 코드>

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int n, arr[200010];

int main()
{
    int i, j;
    scanf("%d", &n);
    for(i=0;i<n;i++) scanf("%d", &arr[i]);
    vector<int> lis;
    lis.push_back(arr[0]);
    for(i=1;i<n;i++) {
        int lb = lower_bound(lis.begin(), lis.end(), arr[i]) - lis.begin();
        int sz = lis.size();
        if(lb >= sz) lis.push_back(arr[i]);
        else lis[lb] = arr[i];
    }
    printf("%d", n - lis.size());
    return 0;
}