2024-03-14

-파일 합치기(13975, 백준)

 쉬운 우선순위 큐 응용 문제이다. 모든 파일들을 하나로 합칠 때의 최소 비용은 항상 가장 작은 수 둘을 합치는 과정을 반복하는 것이다. 따라서 입력받은 수를 최소 우선순위 큐에 넣은뒤, 큐에서 수가 하나남을때까지 두개를 빼서 합친뒤 다시 넣기를 반복해준다. 이 과정에서 발생하는 비용을 처리해주면 된다.

<소스 코드>

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

using namespace std;

int main()
{
	int t;
	scanf("%d", &t);
	while (t--) {
		int i, n;
		scanf("%d", &n);
		priority_queue<long long> pq;
		for (i = 0; i < n; i++) {
			long long x;
			scanf("%lld", &x);
			pq.push(-x);
		}
		long long res = 0;
		while (pq.size() > 1) {
			long long x = -pq.top();
			pq.pop();
			long long y = -pq.top();
			pq.pop();
			pq.push(-(x + y));
			res += x + y;
		}
		printf("%lld\n", res);
	}
}

-서강 그라운드 (14938, 백준)

 쉬운 다익 문제이다. 낙하산에서 떨어진 위치에서부터 주어진 범위 m안에 있는 모든 아이템을 먹을 수 있음으로, 착륙지점에서부터 다익을 돌린다. 그 후, 떨어진 지점에서부터 최소 거리가 m보다 작거나 같은 노드에있는 아이템을 더해준다.

<소스 코드>

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

using namespace std;

int n, m, r;
vector <pair<int, int>> vec[110];
int arr[110], dis[110];

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

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

-면접보는 승범이네(17835, 백준)

 다익 문제이다. 면접장이 여러 군데 존재함으로, 한군데 한군데에서 다익을 돌리면 최악의 경우 O(N^2)으로 시간초과가 떠버릴 수 있기에 모든 면접장을 큐에 먼저 넣어둔 뒤, 다익을 돌리면 된다. 면접장에서부터 집까지의 거리가 아니기 때문에, 노드를 역순으로 집어넣어 직장에서부터 도시까지의 거리를 구하면 답이 나오게 바꾸어 준다.

※숫자의 범위와 초기값에 주의하자.

<소스 코드>

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

using namespace std;

long long n, m, k;
vector <pair<long long, long long>> vec[100010];
priority_queue <pair<long long, long long>> pq;
long long dis[100010];

void Dijkstra()
{
	long long i, j;
	while (!pq.empty()) {
		long long nidx = pq.top().second, nval = -pq.top().first;
		pq.pop();
		if (dis[nidx] < nval) continue;
		for (i = 0; i < vec[nidx].size(); i++) {
			long long idx = vec[nidx][i].first, val = nval + vec[nidx][i].second;
			if (dis[idx] > val) {
				dis[idx] = val;
				pq.push({ -val, idx });
			}
		}
	}
}

int main()
{
	long long i, j;
	scanf("%lld %lld %lld", &n, &m, &k);
	for (i = 1; i <= n; i++) dis[i] = 2e19;
	for (i = 0; i < m; i++) {
		long long x, y, z;
		scanf("%lld %lld %lld", &x, &y, &z);
		vec[y].push_back({ x, z });
	}
	for (i = 0; i < k; i++) {
		long long x;
		scanf("%lld", &x);
		dis[x] = 0;
		pq.push({ 0, x });
	}
	Dijkstra();
	long long mx = -1, ans = 0;
	for (i = 1; i <= n; i++) if (mx < dis[i]) mx = dis[i], ans = i;
	printf("%lld\n%lld", ans, mx);
	return 0;
}

-불켜기(11967, 백준)

 최댈한 불을 얼마나 킬 수 있는지 구하는 문제이다. 무작정 불이 켜진 곳을 넣어주지 말고, 갈 수 있는 지점만 queue에 집어넣어주는 것이 좋다. 불을 킬때, 4방향 탐색을 통해 4방향중 한곳이라도 전에 방문을 했다면 queue에 넣어준다. queue에서 수를 꺼낼 때 또한 4방향 탐색후 불이 켜지지않고, 방문하지 않은 곳을 찾아 queue에 넣어준다. 이렇게 하면 불을 킬 때마다 인접한 4방향을 검사해가며 BFS를 통해 문제를 해결 할 수 있다.

<소스 코드>

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

using namespace std;

int n, m;
vector <pair<int, int>> vec[110][110];
int vis[110][110], light[110][110];
int res;
int dx[5] = { 0, 0, 1, -1 };
int dy[5] = { 1, -1, 0, 0 };

int main()
{
	int i, j;
	scanf("%d %d", &n, &m);
	for (i = 0; i < m; i++) {
		int x, y, a, b;
		scanf("%d %d %d %d", &x, &y, &a, &b);
		vec[x][y].push_back({ a, b });
	}
	queue <pair<int, int>> q;
	q.push({ 1, 1 });
	vis[1][1] = 1;
	light[1][1] = 1;
	res++;
	while (!q.empty()) {
		int n_x = q.front().first, n_y = q.front().second;
		q.pop();
		for (i = 0; i < vec[n_x][n_y].size(); i++) {
			int nx = vec[n_x][n_y][i].first;
			int ny = vec[n_x][n_y][i].second;
			if (light[nx][ny] == 1) continue;
			light[nx][ny] = 1;
			res++;
			for (j = 0; j < 4; j++) {
				int nox = nx + dx[j], noy = ny + dy[j];
				if (nox < 1 || noy < 1 || nox > n || noy > n) continue;
				if (vis[nox][noy] == 1) {
					vis[nx][ny] = 1;
					q.push({ nx, ny });
					break;
				}
			}
		}
		for (i = 0; i < 4; i++) {
			int nx = n_x + dx[i], ny = n_y + dy[i];
			if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
			if (light[nx][ny] == 0 || vis[nx][ny] == 1) continue;
			vis[nx][ny] = 1;
			q.push({ nx, ny });
		}
	}
	printf("%d", res);
	return 0;
}

-가계부(Hard)(12837, 백준)

 세그먼트 트리를 0으로 구성한 후, 주어지는 쿼리에따라 수정과 합 출력을 반복하면 된다. 세그트리를 풀어봤다면 쉽게 풀린다.

<소스 코드>

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

using namespace std;

long long n, Q;
long long segtree[4000010];

long long sum(long long s, long long e, long long low, long long high, long long node) {
    if(e < low || high < s) return 0;
    if(low <= s && e <= high) return segtree[node];
    long long mid = (s + e)/2;
    return sum(s, mid, low, high, node*2) + sum(mid + 1, e, low, high, node*2+1);
}

void edit(long long s, long long e, long long idx, long long node, long long dis)
{
    if(idx < s || idx > e) return;
    segtree[node] += dis;
    if(s != e) {
        long long mid = (s + e) / 2;
        edit(s, mid, idx, node*2, dis);
        edit(mid+1, e, idx, node*2+1, dis);
    }
}

int main()
{
    long long i, j;
    scanf("%lld %lld", &n, &Q);
    for(i=0;i<Q;i++) {
        long long x, y, z;
        scanf("%lld %lld %lld", &x, &y, &z);
        if(x == 1) edit(1, n, y, 1, z);
        else if(x == 2) printf("%lld\n", sum(1, n, y, z, 1));
    }
}