2024-03-07

-선 긋기(2170, 백준)

 간단한 그리디 문제였다. 한선분이 다른 선분의 시작점을 포함하고(겹치고)있다면, 두 선분을 하나의 선분으로 합쳐서 보면 된다. 시작점을 기준으로 정렬을 한 뒤, 앞에서부터 탐색해나간다. 선분의 시작이Si, 끝점이 Ei라면, Si가 현재 이어지고있는 선분안에 포함되며, Ei가 그 선분의 끝점보다길면 갱신해주고 아니라면 ans에 선분의 길이를 더해준다.

<소스 코드>

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

using namespace std;

int n;
int ans;
vector <pair<int, int>> vec;

int main()
{
    int i, j;
    scanf("%d", &n);
    for(i=0;i<n;i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        vec.push_back({x, y});
    }
    sort(vec.begin(), vec.end());
    int e = vec[0].second;
    int s = vec[0].first;
    for(i=1;i<n;i++) {
        if(e < vec[i].first) {
            ans += e - s;
            e = vec[i].second;
            s = vec[i].first;
        }
        else if(s <= vec[i].first && e >= vec[i].first && vec[i].second > e) {
            e = vec[i].second;
        }
    }
    ans += e - s;
    printf("%d", ans);
    return 0;
}

-N번째 큰 수(2075, 백준)

 메모리제한이 빡빡해서 그냥 받고 정렬하니 메모리 초과가 나왔다. 그래서 힙 자료구조를 이용하여, 트리안에 데이터의 수를 N개를 유지해가며 모든 수를 입력받은뒤, 트리의 탑을 출력해줬다.

<소스 코드>

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

using namespace std;

int n;
priority_queue <int> pq;

int main()
{
	int i, j;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			int x;
			scanf("%d", &x);
            pq.push(-x);
            if(pq.size() > n) pq.pop();
		}
	}
	printf("%d", -pq.top());
	return 0;
}

-알고스팟(1261, 백준)

 벽을 최소한으로 부셔야함으로, 벽을 1로두고(이미 1로 입력받는다.) BFS로 최단거리를 구하면 된다. Dijkstra로도 풀린다고 한다. n과 m의 순서에 주의하자.

<소스 코드>

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

using namespace std;

int n, m;
int map[110][110];
int dis[110][110];
int dx[5] = {0, 0, 1, -1};
int dy[5] = {1, -1, 0, 0};

int BFS(int x, int y)
{
    queue<pair<int, int>> q;
    int i, j;
    q.push({x, y});
    dis[x][y] = 0;
    while(!q.empty()) {
        int n_x = q.front().first, n_y = q.front().second;
        q.pop();
        for(i=0;i<4;i++) {
            int nx = n_x + dx[i], ny = n_y + dy[i];
            if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if(dis[nx][ny] > dis[n_x][n_y] + map[nx][ny]) {
                dis[nx][ny] = dis[n_x][n_y] + map[nx][ny];
                q.push({nx, ny});
            }
        }
    }
    return 0;
}

int main()
{
    int i, j;
    scanf("%d %d", &m, &n);
    for(i=0;i<n;i++) {
        for(j=0;j<m;j++) {
            scanf("%1d", &map[i][j]);
            dis[i][j] = 2e9;
        }
    }
    BFS(0, 0);
    /*for(i=0;i<n;i++) {
        for(j=0;j<m;j++) {
            printf("%d ", dis[i][j]);
        }
        printf("\n");
    }*/
    printf("%d", dis[n-1][m-1]);
    return 0;
}

-카드 정렬하기(2170, 백준)

 그리디 + 힙 자료구조를 이용하여 풀었다. 항상 작은 수끼리 더할때, 문제에서 말하는 최소의 비교가 필요하기에 Priority Queue를 잡아주고, 가장 위 두수를 꺼내 비교후 합쳐 다시 넣어주는 과정을 큐에 하나의 수만 남을 때까지 반복해주면 된다.

<소스 코드>

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

using namespace std;

int n;
priority_queue <int> pq;

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

-커피숍2(1275, 백준)

 세그먼트 트리를 이용한 구간합 기초 문제이다. 세그먼트트리를 그냥 가져다 쓰면 고대로 풀린다. 다만 문제에서 x, y의 순서가 반대로 주어질 수 있다 했음으로 그 부분만 주의한다면 어려운 문제는 아니다. 세그 복습할겸 풀어보았다.

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

using namespace std;

long long n, m;
long long arr[100010];
long long segtree[400010];

long long init(long long s, long long e, long long node) {
	if (s == e) return segtree[node] = arr[s];
	long long mid = (s + e) / 2;
	return segtree[node] = init(s, mid, node * 2) + init(mid + 1, e, node * 2 + 1);
}

long long sum(long long s, long long e, long long low, long long high, long long node)
{
	if (e < low || s > high) return 0;
	if (low <= s && high >= e) 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 update(long long s, long long e, long long node, long long idx, long long dis)
{
	if (idx < s || idx > e) return;
	segtree[node] += dis;
	if (s != e) {
		long long mid = (s + e) / 2;
		update(s, mid, node * 2, idx, dis);
		update(mid + 1, e, node * 2 + 1, idx, dis);
	}
}

int main()
{
	long long i, j;
	scanf("%lld %lld", &n, &m);
	for (i = 1; i <= n; i++) scanf("%lld", &arr[i]);
	init(1, n, 1);
	for (i = 0; i < m; i++) {
		int x, y, a, b;
		scanf("%lld %lld %lld %lld", &x, &y, &a, &b);
		long long mx = max(x, y), mn = min(x, y);
		printf("%lld\n", sum(1, n, mn, mx, 1));
		long long dis = b - arr[a];
		update(1, n, 1, a, dis);
		arr[a] = b;
	}
	return 0;
}